1113.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 66 行

/*  This Code is Submitted by wywcgs for Problem 1113 on 2005-10-25 at 01:09:50 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;
const int INFINITE = 2000;

int main()
{
	int phone[MAX][MAX];
	int i, j, k, max, mini, min;
	int n, m, p, time;

	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			for(i = 1; i <= n; i++) {
				for(j = 1; j <= n; j++) {
					if(i == j) {
						phone[i][j] = 0;
					} else {
						phone[i][j] = INFINITE;
					}
				}
			}
			for(i = 1; i <= n; i++) {
				scanf("%d", &m);
				for(j = 0; j < m; j++) {
					scanf("%d %d", &p, &time);
					phone[i][p] = time;
				}
			}
			for(k = 1; k <= n; k++) {
				for(i = 1; i <= n; i++) {
					for(j = 1; j <= n; j++) {
						if(phone[i][k] + phone[k][j] < phone[i][j]) {
							phone[i][j] = phone[i][k] + phone[k][j];
						}
					}
				}
			}
			min = INFINITE;
			for(i = 1; i <= n; i++) {
				max = -1;
				for(j = 1; j <= n; j++) {
					if(phone[i][j] > max) {
						max = phone[i][j];
					}
				}
				if(max < min) {
					min = max;
					mini = i;
				}
			}
			if(min == INFINITE) {
				printf("disjoint\n");
			} else {
				printf("%d %d\n", mini, min);
			}
		}
	}
	
	return 0;
}