PKU 1125 Stockbroker Grapevine

• 全点間最短距離
• ダイクストラ法またはワーシャルフロイド法が使える

static int g[128][128];
int main() {
	for (int N; cin >> N && N; ) {
		fill_n((int*)g, sizeof(g) / sizeof(g[0][0]), INT_MAX / 2);

		for (int n = 1; n <= N; ++n) {
			int M;
			cin >> M;
			for (int m = 0; m < M; ++m) {
				int to, cost;
				cin >> to >> cost;
				g[n][to] = cost;
			}
		}

		for (int k = 1; k <= N; ++k) {
			for (int i = 1; i <= N; ++i) {
				for (int j = 1; j <= N; ++j) {
					g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
				}
			}
		}

		int bestPerson = -1;
		int bestTime = INT_MAX;
		for (int i = 1; i <= N; ++i) {
			int maxTime = -1;
			for (int j = 1; j <= N; ++j) {
				if (i == j) {
					continue;
				}
				maxTime = max(maxTime, g[i][j]);
			}
			
			if (bestTime > maxTime) {
				bestTime = maxTime;
				bestPerson = i;
			}
		}

		if (bestTime == INT_MAX / 2) {
			printf("disjoint\n");
		} else {
			printf("%d %d\n", bestPerson, bestTime);
		}
	}
}