ACdream 1209 群赛D qj的招待会(flyod)

ACdream 1209 群赛D qj的招待会(flyod)"/>

ACdream 1209 群赛D qj的招待会(flyod)

题目链接：http://115.28.76.232/contest?cid=1115#problem-D

Problem Description

终于，qj不负众望的拿到了爱情。
但是其他村子的人都不相信这个注定孤独一生的孩子居然会拥有爱情，于是都决定到qj所在的村子里去看看是否真的如此。
这时，qj为了（xiu）招（en）待（ai），他就必须得知道他们最早什么时候到，并且是哪个村子的。
qj所在的村子会用'Z'来代表，其他人的村子被标记为'a'..'z'和'A'..'Y',在用大写字母表示的村子中有人,小写字母中则没有。
为了使问题简单化，设定这些人每分钟走1km（喂喂，这可能吗！！！）
他现在很忙，正在和爱情约会中，所以请各位帮帮qj算算吧。

Input

第一行 N表示道路数量(1<= N<=10000),

第2-N+1行 用空格隔开的两个字母和整数代表道路连接的村子与道路的长度(km)(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

分析： FLYOD,注意重边取最小的

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;const int maxn = 125;int mp[maxn][maxn];int main()
{int n;while(~scanf("%d",&n)){getchar();for(int i=60;i<maxn;i++){for(int j=60;j<maxn;j++)mp[i][j]=1000000000;}char a,b;int c;for(int i=0;i<n;i++){scanf("%c",&a);getchar();scanf("%c",&b);scanf("%d",&c);getchar();mp[a][b]=mp[b][a]=min(c,mp[a][b]);}for(int k=60;k<maxn;k++)for(int i=60;i<maxn;i++)for(int j=60;j<maxn;j++){if(mp[i][k]==1000000000||mp[k][j]==1000000000)continue;if(mp[i][k]+mp[k][j]<mp[i][j])mp[i][j]=mp[i][k]+mp[k][j];}int minn = 1000000000;char dis='Z';char ans;for(char i='A'; i<='Y' ;i++)if(mp[i][dis]<minn)minn=mp[i][dis],ans=i;//cout<<i<<" "<<mp[i][dis]<<endl;printf("%c %d\n",ans,minn);}return 0;
}