Floyd最短路径

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define maxn 155
 5 #define INF 0xffffff
 6 using namespace std;
 7 int map[maxn][maxn];
 8 char s1[10005][40],s2[10005][40],s[10005][40];
 9 int t[10005];
10 int n,cnt=0;
11 int  solve(char *p)
12 {
13     for(int i=1;i<=cnt;i++)
14         if(strcmp(s[i],p)==0)
15         return i;
16     strcpy(s[++cnt],p);
17         return cnt;
18 }
19 int main()
20 {
21     //freopen("in.txt","r",stdin);
22     char start[40],end[40];
23     while(scanf("%d",&n)!=EOF)
24     {
25         if(n==-1)  break;
26         cnt=0;
27         scanf("%s%s",start,end);
28         for(int i=1;i<=n;i++)
29             scanf("%s%s%d",s1[i],s2[i],&t[i]);
30         for(int i=1;i<maxn;i++)
31         {
32             map[i][i]=0;
33             for(int j=1;j<maxn;j++)
34                 map[i][j]=INF;
35         }
36         if(!strcmp(start,end))
37         {
38             printf("0\n");
39             continue;
40         }
41 
42         for(int i=1;i<=n;i++)
43         {
44             int x=solve(s1[i]);
45             int y=solve(s2[i]);
46             map[x][y]=map[y][x]=t[i];
47         }
48         int s=solve(start);
49         int e=solve(end);
50         for(int i=1;i<=cnt;i++)
51             for(int j=1;j<=cnt;j++)
52             for(int k=1;k<=cnt;k++)
53             map[j][k]=min(map[j][i]+map[i][k],map[j][k]);
54         if(map[s][e]==INF)
55             printf("-1\n");
56         else
57             printf("%d\n",map[s][e]);
58     }
59     return 0;
60 }