POJ 1125 Stockbroker Grapevine

題意：
    N表示共N個點，然後底下N行，第i行第一個數字t表示後面有t個pair，每個pair兩個數字分別代表x, w，i點到x點距離w，注意這是單向道路。題目求從哪個點當作起點可以使得該點走到距離該點最遠的距離為最短。假設i點作起點，走到距離i點最遠的那個點距離為Di，求所有Di中最小的那個值，輸出i及Di。另外題目要求這個i點需要能夠到達所有其他的點。
想法：
    先做Floyd演算法，再去找每個點i的Di，在從Di中選出最小的那個去輸出i及Di即可，注意要判斷這個i是否能到達所有除了i以外的點。

	#include <cstdio>
	using namespace std;
	#define INF 99999999
	int Dis[101][101];
	int main()
	{
	int N;
	while (scanf("%d", &N) && N) {
	//Initial
	for (int i = 1; i <= N; ++i) {
	for (int j = 1; j <= N; ++j)
	Dis[i][j] = INF;
	Dis[i][i] = 0;
	}
	// Input
	for (int i = 1; i <= N; ++i) {
	int t, x, w;
	scanf("%d", &t);
	for (int j = 0; j < t; ++j) {
	scanf("%d %d", &x, &w);
	Dis[i][x] = w;
	}
	}
	// Floyd Algorithm
	for (int k = 1; k <= N; ++k)
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= N; ++j)
	if (Dis[i][k] + Dis[k][j] < Dis[i][j])
	Dis[i][j] = Dis[i][k] + Dis[k][j];
	// Analysis
	int Min = INF;
	int Min_pos;
	bool Disjoint = true;
	for (int i = 1; i <= N; ++i) {
	int Max_length = 0; // i點到其他點的最大距離(不包含INF)
	bool Reachable = true;
	for (int j = 1; j <= N; ++j) {
	if (Dis[i][j] == INF) {
	Reachable = false;
	break;
	}
	else if (Dis[i][j] > Max_length)
	Max_length = Dis[i][j];
	}
	if (Reachable == true) {
	Disjoint = false;
	if (Max_length < Min) {
	Min = Max_length;
	Min_pos = i;
	}
	}
	}
	// Output
	if (Disjoint) puts("disjoint");
	else printf("%d %d\n", Min_pos, Min);
	}
	}

view raw [POJ] 1125 Stockbroker Grapevine.cpp hosted with ❤ by GitHub