学步园

题意是：在一个城市里有一些消防站，但是市民抱怨这些消防站离他们太远了，希望政府能新建一些消防站，让他们离这些新建的消防站比原有的消防站近一些。

思路：可以利用Floyd求出各点之间的最短距离，然后枚举每个点，若该点比原有的点的最大值要小，则更新，直至最小

#include <iostream>
#include <cstdio>
#include <cstring>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define inf 9999999
#define maxn 512

using namespace std;

int map[maxn][maxn];
int firehouse[maxn];
int firewight[maxn];
int node,renode;

void init()
{
	for(int i=0;i<maxn;i++)
	{
		for(int j=0;j<maxn;j++)
		{
			map[i][j]=inf;
		}
		map[i][i]=0;
	}

}

void Floyd()
{
	int i,k,j;
	for(k=1;k<=node;k++)
		for(i=1;i<=node;i++)
			for(j=1;j<=node;j++)
				map[i][j]=min(map[i][j],map[i][k]+map[k][j]);

}

void solve()
{

	scanf("%d %d",&renode,&node);
	for(int i=1;i<=renode;i++)
	{
		scanf("%d",&firehouse[i]);
	}
	init();
	int st,end,val;
	while(scanf("%d %d %d",&st,&end,&val)!=EOF)
	{
		if(map[st][end]>val)
			map[st][end]=map[end][st]=val;
	}

	Floyd();
	int remin=0,temp;
	for(int i=1;i<=node;i++)
	{
		temp=inf;
		for(int j=1;j<=renode;j++)
		{
			temp=min(temp,map[i][firehouse[j]]);
		}
		firewight[i]=temp;
		if(remin<firewight[i])
			remin=firewight[i];
	}
	int ansidx=1,maxnu;
	for(int i=1;i<=node;i++)
	{
		maxnu=0;
		for(int j=1;j<=node;j++)
		{

			if(map[i][j]<firewight[j])
			{
				maxnu=max(maxnu,map[i][j]);
			}else
			{
				maxnu=max(maxnu,firewight[j]);
			}

		}
		if(maxnu<remin)
		{
			remin=maxnu;
			ansidx=i;
		}


	}
	printf("%d\n",ansidx);
}
int main()
{
	solve();
	return 0;
}