pku1125.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define SIZE 101
#define TheMax 100000
int Time[SIZE][SIZE];
int N, p, t;

void pre()
{
	int i, j;
	for (i = 1; i <= N; i++)
	{
		Time[i][i] = 0;
		for (j = i + 1; j <= N; j++)
		{
			Time[i][j] = Time[j][i] = TheMax;
		}
	}
}

void floyd()
{
	int i, j, k, min, max, minid;
	for (k = 1; k <= N; k++)
	{
		for (i = 1; i <= N; i++)
		{
			for (j = 1; j <= N; j++)
			{
				if (Time[i][j] > Time[i][k] + Time[k][j])
				{
					Time[i][j] = Time[i][k] + Time[k][j];
				}
			}
		}
	}
	for (i = 1, p = 1, t = TheMax; i <= N ; i++)
	{
		for (j = 1, max = 0; j <= N; j++)
		{
			if (Time[i][j] > max)
			{
				max = Time[i][j];
			}
		}
		if (max < t)
		{
			t = max;
			p = i;
		}
	}
}

int main()
{
	int i, j, n;

	while (scanf("%d", &N) != -1 && N > 0)
	{
		if (N == 1)
		{
			printf("1 0\n");
			continue;
		}

		pre();

		for (i = 0; i < N; i++)
		{
			scanf("%d", &n);
			for (j = 0; j < n; j++)
			{
				scanf("%d%d", &p, &t);
				Time[i + 1][p] = t;
			}
		}

		floyd();

		printf("%d %d\n", p, t);
	}
	
	return 0;
}