3115984_ac_2779ms_1132k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#define INF 2100000000

int mark[501];
int map[501][501];

void floyd(int Q)
{
	int i, j, k;
 
	for(k = 0; k < Q; k++)
	{
		for(i = 0; i < Q; i++)
		{
			if(map[i][k]!=INF)
			{
				for(j = 0; j < Q; j++)
					if(map[i][k]+map[k][j]<map[i][j])
						map[i][j]=map[i][k]+map[k][j]; 
			}
		}  
	}
}

int main()
{
	int f, i, j, t;
	int a, b, w, k;

	scanf("%d%d",&f,&i);
	for(j = 0; j < i; j++)
	{
		for(k = 0; k < i; k++)
		{
			if(k==j)
				map[k][j] = 0;
			else
				map[j][k] = INF;
		}
		mark[j] = 0;
	}
	for(j = 0; j < f; j++)
	{
		scanf("%d",&t);
		mark[t-1] = 1;
	}
	while(scanf("%d%d%d",&a,&b,&w)==3)
	{
		a--;b--;
		if(w < map[a][b])
		{
			map[a][b] = map[b][a] = w;
		}
	}
	floyd(i);
	int max, min, tt, kk, ans;
	ans = INF+1;
	for(j = 0; j < i; j++)
	{
		tt = mark[j];
		mark[j] = 1;
		max = -1;
		for(k = 0; k < i; k++)
		{
			min = INF;
			for(t = 0; t < i; t++)
			{
				if(mark[t]&&map[k][t]<min)
					min = map[k][t];
			}
			if(min > max)
				max = min;
		}
		if(max < ans)
		{
			ans = max;
			kk = j+1;
		}
		mark[j] = tt;
	}
	printf("%d\n",kk);
	return 0;
}