现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时，两个牧场(可能是自我相同的)之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。牧场被标记为'a'..'z'和'A'..'Y',在用大写字母表示的牧场中有一只母牛,小写字母中则没有。谷仓的标记是'Z',注意没有母牛在谷仓中。 注意'm'和'M'不是一个牧场
格式
PROGRAM NAME: comehome
INPUT FORMAT
(file comehome.in)
第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。
第 2 ..P+1行: 用空格分开的两个字母和一个整数:
被道路连接牧场的标记和道路的长度(1<=长度<=1000)。
SAMPLE OUTPUT
(file comehome.out)
单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。
SAMPLE INPUT
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
SAMPLE OUTPUT
B 11
【参考程序】：
/*
ID: XIONGNA1
PROG: comehome
LANG: C++
*/
#include<iostream>
using namespace std;
int cost[53][53],lowcost[53];
bool bo[53];
int n,ans;
void dijkstra()
{
int MIN,k;
for (int i=1;i<=51;i++)
{
MIN=0xFFFFFFF;
for (int j=1;j<=52;j++)
if (!bo[j] && lowcost[j]<MIN)
{
MIN=lowcost[j];
k=j;
}
if (MIN==0xFFFFFFF) return ;
bo[k]=true;
for (int j=1;j<=52;j++)
if (!bo[j] && lowcost[j]>lowcost[k]+cost[k][j])
lowcost[j]=lowcost[k]+cost[k][j];
}
}
int main()
{
freopen("comehome.in","r",stdin);
freopen("comehome.out","w",stdout);
scanf("%d",&n);getchar();
for (int i=1;i<=52;i++)
for (int j=1;j<=52;j++)
if (i==j) cost[i][j]=0;
else cost[i][j]=0xFFFFFFF;
char ch1,t,ch2; int x,y,c;
for (int i=1;i<=n;i++)
{
scanf("%c%c%c%d",&ch1,&t,&ch2,&c);
if (ch1>='A' && ch1<='Z') x=(ch1-64);
else x=(ch1-96)+26;
if (ch2>='A' && ch2<='Z') y=(ch2-64);
else y=(ch2-96)+26;
if (cost[x][y]>c)//防止重边
{
cost[x][y]=c; cost[y][x]=c;
}
getchar();
}
for (int i=1;i<=52;i++)
{
lowcost[i]=cost[26][i];
bo[i]=false;
}
bo[26]=true;
dijkstra();
int ans=0xFFFFFFF,p;
for (int i=1;i<=25;i++)
if (ans>lowcost[i])
{
ans=lowcost[i]; p=i;
}
printf("%c %d\n",char(p+64),ans);
return 0;
}