HDU

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

Sample Input
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
 

Sample Output
50


Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake

题意：

求最短路，要注意的是顶点名称都换成了字符串，要重新标记，还有就是起点和终点重合的情况需要考虑。

*：使用map函数可以将字符串转化为整数存储。

map<string,int>mymap;

mymap[string]=int;

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stack>
  6 #include<math.h>
  7 #include<queue>
  8 #include<map>
  9 using namespace std;
 10 
 11 ///map可以理解为一个一对一的key，value对，也叫做键值对
 12 ///通常用于快速寻找一个key的对应的value是多少
 13 ///map<key,value>mymap; mymap[key]=value;
 14 
 15 #define INF 0x3f3f3f3f
 16 #define N 12342
 17 
 18 int n;
 19 int s[200][200];
 20 int p[200],t[200];
 21 
 22 void Dij(int e,int f)
 23 {
 24    memset(p,0,sizeof(p));
 25 
 26     for(int i=1;i<=f;i++)
 27         t[i]=(i==e?0:INF);
 28 
 29     for(int i=1;i<=f;i++)
 30     {
 31         int Min=INF,w;
 32 
 33         for(int j=1;j<=f;j++)
 34             if(!p[j]&&t[j]<Min)
 35             {
 36                  w=j;
 37                  Min=t[j];
 38             }
 39         p[w]=1;
 40         if(Min==INF) break;
 41 
 42         for(int j=1;j<=f;j++)
 43         {
 44             if(!p[j]&&t[w]+s[w][j]<t[j])
 45             t[j]=t[w]+s[w][j];
 46         }
 47     }
 48 }
 49 
 50 int main()
 51 {
 52     int flag,len;
 53 
 54     map<string,int> mymap;///将字符串化为整数存储，然后进行Dij
 55     char s1[100],s2[100];
 56 
 57     while(scanf("%d", &n))
 58     {
 59         if(n==-1) break;
 60         mymap.clear();///mymap清零
 61 
 62         memset(s,INF,sizeof(s));
 63         flag=0;
 64 
 65         scanf("%s%s", s1,s2);
 66 
 67         ///strcmp用于比较两个字符串
 68         ///s1<s2,返回负数；s1==s2,返回0；s1>s2,返回正数
 69         if(strcmp(s1,s2)==0)
 70             flag=1;
 71 
 72         mymap[s1]=1;
 73         mymap[s2]=2;
 74         int cnt=3;
 75 
 76        /// printf("%d %d
", s[1][2], s[6][6]);
 77 
 78         for(int i=0; i<n; i++)
 79         {
 80             scanf("%s%s%d", s1,s2,&len);
 81 
 82             if(mymap[s1]==0)
 83                 mymap[s1]=cnt++;
 84             if(mymap[s2]==0)
 85                 mymap[s2]=cnt++;
 86             s[mymap[s1]][mymap[s2]]= s[mymap[s2]][mymap[s1]]=min(len, s[mymap[s1]][mymap[s2]]);
 87 
 88             ///printf("%d %d %d
", mymap[s1],mymap[s2],len);
 89         }
 90 
 91         if(flag)
 92         {
 93             printf("0
");
 94             continue;
 95         }
 96 
 97         Dij(1,cnt);
 98 
 99         printf("%d
", t[2]==INF?-1:t[2]);
100     }
101     return 0;
102 }

本人博客：http://www.cnblogs.com/weiyuan/