记录编号	321668	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2016-10-13 20:59:39	内存使用	1.70 MiB

#include <stdio.h>
#include <iostream>
#include <string.h>
using std::cin;
using std::cout;

template <typename T> inline void Read(T &num) {
	num = 0; char ch; bool minus = false;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') minus = true, ch = getchar();
	while (num = num * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	if (minus) num = -num;
}

char cow[10010];
int num = 0;
int dis[600][600];

int main() {
 #define SUBMIT
 #ifdef SUBMIT
	freopen("comehome.in", "r", stdin);
	freopen("comehome.out", "w", stdout);
 #endif

	int n; cin >> n;
	memset(dis, 0x3f, sizeof(dis));
	char c1, c2;
	int u, v, w;
	for (int i = 1; i <= n; ++i) {
		cin >> c1;
		if (c1 < 'Z') cow[num++] = c1;
		cin >> c2;
		if (c2 < 'Z') cow[num++] = c2;
		u = c1 - 'A'; v = c2 - 'A'; cin >> w;
		if (w < dis[u][v]) dis[u][v] = dis[v][u] = w;
	}
	for (int i = 0; i < 58; ++i) dis[i][i] = 0;
	for (int k = 0; k < 58; ++k)
		for (int i = 0; i < 58; ++i)
			for (int j = 0; j < 58; ++j)
				if (dis[i][j] > dis[i][k] + dis[k][j])
					dis[i][j] = dis[i][k] + dis[k][j];
	int ans = 0x3f3f3f3f; char pos;
	for (int i = 0; i < num; ++i)
		if (cow[i] != 'Z' && dis[cow[i] - 'A'][25] < ans)
			{ ans = dis[cow[i] - 'A'][25]; pos = cow[i]; }
	cout << pos << ' ' << ans << '\n';

 #ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
 #else
	fclose(stdin); fclose(stdout);
 #endif
	return 0;
}