Posted on 2009-04-23 18:44
superman 阅读(66)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 //a..z -> 0..25
7 //A..Y -> 26..51
8
9 int main()
10 {
11 freopen("comehome.in", "r", stdin);
12 freopen("comehome.out", "w", stdout);
13
14 int n;
15 cin >> n;
16
17 int map[52][52] = { 0 };
18
19 bool x[52] = { false };
20
21 char s, t; int l;
22 for (int i = 0; i < n; i++)
23 {
24 cin >> s >> t >> l;
25
26 if (s >= 'a' && s <= 'z')
27 s -= 'a';
28 else
29 s -= 'A' - 26;
30
31 if (t >= 'a' && t <= 'z')
32 t -= 'a';
33 else
34 t -= 'A' - 26;
35
36 x[s] = x[t] = true;
37
38 int a = map[s][t];
39 int b = map[t][s];
40 int c;
41
42 if (a == 0) a = INT_MAX;
43 if (b == 0) b = INT_MAX;
44 c = min(a, b);
45
46 map[s][t] = map[t][s] = min(c, l);
47 }
48
49 //spfa
50 queue <int> q;
51 int f[52];
52
53 q.push(51);
54 f[51] = 0;
55 for (int i = 0; i < 51; i++)
56 f[i] = INT_MAX;
57
58 while (q.empty() == false)
59 {
60 int cp = q.front(); q.pop();
61
62 for (int i = 0; i < 51; i++)
63 if (x[i] && map[cp][i] && f[cp] + map[cp][i] < f[i])
64 {
65 f[i] = f[cp] + map[cp][i];
66 q.push(i);
67 }
68 }
69
70 int ans = INT_MAX;
71 char c;
72 for (int i = 26; i < 51; i++)
73 if (x[i] && f[i] < ans)
74 {
75 ans = f[i];
76 c = i - 26 + 'A';
77 }
78
79 cout << c << ' ' << ans << endl;
80
81 return 0;
82 }
83