hdu 2112 HDU Today （最短路）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112

题目大意：给出起点和终点，然后算出最短的路。

不过有好多细节要注意：

(1)起始点和终止点相等的时候，这里注意不能直接输出0，必须用标记，因为数据可能还没有处理完!!!此处贡献n次wa。

(2)这里是某大神教我的用map进行转换，将字符串转换成数字，值得参考。map<string,int>M,V；不过这里同样是wa了好多次。要注意的是将最先输入的开始和结束的点也要放到这个map里面。

(3)再就是注意的dijkstra这个算法的应用了。

祝大家好运~wa了14次的我眼泪掉下来。。。。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <map>
  4 #include <cstring>
  5 #include <algorithm>
  6 using namespace std;
  7 #define INF 9999999
  8 int k,Map[155][155],node[155];
  9 map<string,int>M,V;
 10 
 11 void set()
 12 {
 13     for (int i=0; i<155; i++)
 14     {
 15         node[i]=INF;
 16         for (int j=0; j<155; j++)
 17         {
 18             if (i!=j)
 19                 Map[i][j]=INF;
 20             else
 21                 Map[i][j]=0;
 22         }
 23     }
 24 }
 25 
 26 void dijkstra(int m)
 27 {
 28     int vis[155]= {0};
 29     int tm=m;
 30     vis[m]=1;
 31     node[m]=0;
 32     for (int j=1; j<k; j++)
 33     {
 34         int Min=INF;
 35         for (int i=0; i<k; i++)
 36             if (!vis[i])
 37             {
 38                 if (node[i]>node[tm]+Map[tm][i])
 39                     node[i]=node[tm]+Map[tm][i];
 40                 if (Min>node[i])
 41                 {
 42                     Min=node[i];
 43                     m=i;
 44                 }
 45                 //cout<<i<<" "<<node[i]<<" "<<Map[tm][i]<<endl;
 46             }
 47         vis[m]=1;
 48         tm=m;
 49     }
 50 }
 51 
 52 int main()
 53 {
 54     bool flag;
 55     int t,n;
 56     while (scanf("%d",&n),n!=-1)
 57     {
 58         flag=0;
 59         M.clear();
 60         V.clear();
 61         set();
 62         //memset(Map,INF,sizeof(Map));
 63         char start[135],end[135],s[135],e[135];
 64         k=2;
 65         scanf("%s%s",start,end);
 66         if (strcmp(start,end)==0)
 67             flag=1;
 68         if(n==0)
 69         {
 70             printf("-1
");
 71             continue;
 72         }
 73         M[start]=0;
 74         M[end]=1;
 75         while (n--)
 76         {
 77             scanf("%s%s%d",s,e,&t);
 78             if(!V[s])
 79             {
 80                 V[s]=1;
 81                 M[s]=k++;
 82                 //cout<<k<<endl;
 83             }
 84             if(!V[e])
 85             {
 86                 V[e]=1;
 87                 M[e]=k++;
 88                 //cout<<k<<endl;
 89             }
 90             if (Map[M[s]][M[e]]>t)
 91                 Map[M[s]][M[e]]=Map[M[e]][M[s]]=t;
 92         }
 93         //set();
 94         //cout<<k<<endl;
 95         if (flag)
 96         {
 97             printf ("0
");
 98             continue;
 99         }
100         dijkstra(M[start]);
101         if(node[M[end]]==INF)
102             printf ("-1
");
103         else
104             printf ("%d
",node[M[end]]);
105     }
106     return 0;
107 }

View Code

hdu 2112 HDU Today （最短路）

相关推荐