USACO 2.4.4 Bessie Come Home 回家（最短路）

Description

现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时，两个牧场(可能是自我相同的)之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。牧场被标记为'a'..'z'和'A'..'Y',在用大写字母表示的牧场中有一只母牛,小写字母中则没有。谷仓的标记是'Z',注意没有母牛在谷仓中。

Input

第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。第 2 ..P+1行: 用空格分开的两个字母和一个整数: 被道路连接牧场的标记和道路的长度(1<=长度<=1000)。

Output

单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。

Sample Input

5

A d 6

B d 3

C e 9

d Z 8

e Z 3

Sample Output

B 11

解题思路：最短路问题，因为牧场最多只有52个，可以看出多源最短路，使用Floyd算法；但同样的是终点只有一个，要求的是所有起点到终点中的
最短路，我们完全可以反其道而行之，看出单源最短路问题，将终点看出起点，使用Dijkstra算法，利用其中的dis[]数组，找到终点到起点各点中
距离最短的即可。

Floyd算法

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 const int INF =1e8;

 using namespace std;

 int n;

 int flag[];

 int maps[][];

 void Floyd()

 {

     int i,j,k;

     for (k = 'A'; k <= 'z'; k++)

     {

         for (i = 'A'; i <= 'z'; i++)

         {

             for (j = 'A'; j <= 'z'; j++)

             {

                 maps[i][j]=min(maps[i][j],maps[i][k]+maps[k][j]);

             }

         }

     }

 }

 int main()

 {

     char a,b;

     int c,i,j;

     int ans = INF;

     char ans1;

     for (i='A';i<='z';i++)

     {

         for (j ='A';j<='z';j++)

         {

             if (i!=j)

             {

                 maps[i][j]=INF;

             }

         }

     }

     scanf("%d",&n);

     getchar();

     for (i = ; i <= n; i++)

     {

         scanf("%c %c",&a,&b);

         scanf("%d",&c);

         getchar();

         if (a >= 'A' && a <= 'Z')

         {

             flag[a] = ;

         }

         if (b >= 'A' && b <= 'Z')

         {

             flag[b]=;

         }

         maps[a][b]=maps[b][a]=min(c,maps[a][b]);

     }

     Floyd();

     for (i ='A'; i<='Y'; i++)

     {

         if (flag[i]&&maps[i]['Z']<ans)

         {

             ans = maps[i]['Z'];

             ans1 = char(i);

         }

     }

     printf("%c %d\n",ans1,ans);

     return ;

 }

Dijkstra算法

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 const int INF =1e8;

 using namespace std;

 int n;

 int vis[];

 int flag[];

 int dis[];

 int maps[][];

 void Dijstra()

 {

     int i,j,pos=,mins,sum=;

     for(i='A'; i<='z'; ++i)

     {

         dis[i]=maps[][i];

     }

     vis[]=-;

     dis[]=;

     for(i='A'; i<'z'; i++)

     {

         mins=INF;

         for(j='A'; j<='z'; ++j)

         {

             if(!vis[j]&&mins>dis[j])

             {

                 mins=dis[j];

                 pos=j;

             }

         }

         vis[pos]=-;

         for(j='A'; j<='z'; ++j)

         {

             if(!vis[j]&&dis[j]>dis[pos]+maps[pos][j])

             {

                 dis[j]=dis[pos]+maps[pos][j];

             }

         }

     }

     return ;

 }

 int main()

 {

     char a,b;

     int c,i,j;

     int ans = INF;

     char ans1;

     memset(vis,-,sizeof(vis));

     for (i='A'; i<='z'; i++)

     {

         for (j='A'; j<='z'; j++)

         {

             if(i!=j)

             {

                 maps[i][j]=INF;

             }

             else

             {

                 maps[i][i]=;

             }

         }

     }

     scanf("%d",&n);

     getchar();

     for (i = ; i <= n; i++)

     {

         scanf("%c %c",&a,&b);

         scanf("%d",&c);

         getchar();

         for(j='A';j<='z';j++)

         {

             vis[a]=;

         }

         for(j='A';j<='z';j++)

         {

             vis[b]=;

         }

         maps[a][b]=maps[b][a]=min(c,maps[a][b]);

     }

     Dijstra();

     ans=INF;

     for(i='A';i<='Y';i++)

     {

         if(dis[i]<ans)

         {

             ans=dis[i];

             ans1=i;

         }

     }

     printf("%c %d\n",ans1,ans);

     return ;

 }

巴特西