pku2607.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 115 行

#include <stdio.h>
#define size 510
#define TheMax 100000000
int D[size][size];
int F, I;
int Min[size];

int MinVal(int x, int y)
{
	return x < y ? x : y;
}

void init()
{
	int i, j;
	for (i = 0; i < I; i++)
	{
		Min[i] = TheMax;
		for (j = i + 1; j < I; j++)
		{
			D[i][j] = D[j][i] = TheMax;
		}
		D[i][i] = 0;
	}
}

void Floyd()
{
	int i, j, k;
	for (k = 0; k < I; k++)
	{
		for (i = 0; i < I; i++)
		{
			for (j = i + 1; j < I; j++)
			{
				if (D[i][j] > D[i][k] + D[k][j])
				{
					D[i][j] = D[j][i] = D[i][k] + D[k][j];
				}
			}
		}
	}
}

void FindMin()
{
	int i, j;
	for (i = 0; i < I; i++)
	{
		if (Min[i] == 0)
		{
			continue;
		}
		for (j = 0; j < I; j++)
		{
			if (Min[j] == 0)
			{
				if (Min[i] > D[i][j])
				{
					Min[i] = D[i][j];
				}
			}
		}
	}
}

int main()
{
	int i, j, k, tmp, f;
	int s, e, d;
	int maxdis, minid, minmax;
	scanf("%d %d", &F, &I);
	init();
	while (F--)
	{
		scanf("%d", &f);
		Min[f - 1] = 0;
	}
	while (scanf("%d %d %d", &s, &e, &d) != -1)
	{
		s--;
		e--;
		if (D[s][e] > d)
		{
			D[s][e] = D[e][s] = d;
		}
	}
	Floyd();
	
	FindMin();
	
	minid = -1;
	minmax = TheMax;

	for (i = 0; i < I; i++)
	{
		for (j = 0, maxdis = 0; j < I; j++)
		{
			tmp = MinVal(Min[j], D[i][j]);
			if (maxdis < tmp)
			{
				maxdis = tmp;
			}
		}
		if (maxdis < minmax)
		{
			minmax = maxdis;
			minid = i;
		}
	}
	printf("%d\n", minid + 1);
	return 0;
}