USACO 2.4 Bessie Come(最短)
9588 ワード
水問題、無方向に気づかなかった、2 Y.
1 /*
2 ID: cuizhe
3 LANG: C++
4 TASK: comehome
5 */
6 #include <iostream>
7 #include <cstdio>
8 #include <cstring>
9 #include <cmath>
10 #include <algorithm>
11 using namespace std;
12 #define N 100000000
13 int p[101][101];
14 int judge(char ch)
15 {
16 if(ch >= 'A'&&ch <= 'Z')
17 return ch-'A'+1;
18 else
19 return ch-'a'+27;
20 }
21 int main()
22 {
23 int i,j,k,n,sv,ev,w,ans,t;
24 freopen("comehome.in","r",stdin);
25 freopen("comehome.out","w",stdout);
26 char n1[2],n2[2];
27 scanf("%d",&n);
28 for(i = 1;i <= 52;i ++)
29 {
30 for(j = 1;j <= 52;j ++)
31 p[i][j] = N;
32 p[i][i] = 0;
33 }
34 for(i = 1;i <= n;i ++)
35 {
36 scanf("%s%s%d",n1,n2,&w);
37 sv = judge(n1[0]);
38 ev = judge(n2[0]);
39 if(p[sv][ev] > w)
40 {
41 p[sv][ev] = w;
42 p[ev][sv] = w;
43 }
44 }
45 for(i = 1;i <= 52;i ++)
46 {
47 for(j = 1;j <= 52;j ++)
48 {
49 for(k = 1;k <= 52;k ++)
50 {
51 if(p[j][k] > p[j][i]+p[i][k])
52 p[j][k] = p[j][i]+p[i][k];
53 }
54 }
55 }
56 ans = N;
57 for(i = 1;i <= 25;i ++)
58 {
59 if(ans > p[i][26])
60 {
61 ans = p[i][26];
62 t = i;
63 }
64 }
65 printf("%c %d
",t+'A'-1,ans);
66 return 0;
67 }