1211.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1211 on 2005-10-05 at 23:53:50 */ 
#include <cstdio>
#define  MAX  128
#define  LIMIT  50000000

int main()
{
	int i, j, k, l, test;
	int pathN, vn, mv;
	int a, b;
	long path[MAX][MAX], min, sum;
	
	scanf("%d", &test);
	for(l = 0; l < test; l++) {
		for(i = 0; i < MAX; i++) {
			for(j = 0; j < MAX; j++) {
				path[i][j] = LIMIT;
			}
		}
		scanf("%d %d", &vn, &pathN);
		for(i = 0; i < pathN; i++) {
			scanf("%d %d", &a, &b);
			scanf("%ld", &path[a][b]);
			path[b][a] = path[a][b];
		}
		for(k = 0; k < vn; k++) {
			for(i = 0; i < vn; i++) {
				for(j = 0; j < vn; j++) {
					if(path[i][k]+path[k][j] < path[i][j]) {
						path[i][j] = path[i][k] + path[k][j];
					}
				}
			}
		}
		min = LIMIT;
		for(i = 0; i < vn; i++) {
			sum = 0;
			for(j = 0; j < vn; j++) {
				if(i != j) {
					sum += path[i][j];
				}
			}
			if(min > sum) {
				min = sum;
				mv = i;
			}
		}
		printf("%d %ld\n", mv, min);
	}
	
	return 0;
}