1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 160;
char s1[maxn], s2[maxn];
int d[maxn][maxn];
inline int C(char c) {
return c < 'a' ? c - 'A' + 26 : c - 'a';
}
int main() {
freopen("comehome.in", "r", stdin);
freopen("comehome.out", "w", stdout);
memset(d, 0x3f, sizeof d);
int p;
scanf("%d", &p);
for (int i = 0; i < p; ++i) {
int len;
scanf("%s%s%d", s1, s2, &len);
int u = C(s1[0]), v = C(s2[0]);
d[u][v] = d[v][u] = min(d[u][v], len);
}
for (int k = 0; k < 52; ++k) {
for (int i = 0; i < 52; ++i) {
for (int j = 0; j < 52; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
int Min = 0x3f3f3f3f, ans = 0;
for (int i = 26; i < 51; ++i) {
if (d[i][51] < Min) {
Min = d[i][51], ans = i;
}
}
printf("%c %d\n", ans + 'A' - 26, Min);
return 0;
}
|