记录编号	386727	评测结果	AAAAAAAA
题目名称	服务点设置	最终得分	100
用户昵称	xzcxzc11	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2017-03-25 00:09:03	内存使用	13.70 MiB

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#define DEBUG

using namespace std;

const int INF=200000;
const int maxn=100;
int n,m,vh;
int v[maxn]={0};
int w[maxn][maxn]={{0}};
int father[maxn+1]={0};
int d[maxn];
int res[maxn];

void dijkstra();
void print(int p);

int main()
{
	freopen("djsa.in","r",stdin);
	freopen("djsa.out","w",stdout);
	cin>>n>>m;
	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j)
			w[i][j]=INF;
	int s,f,dis;
	for (int i=0;i<m;++i)
	{
		cin>>s>>f>>dis;
		w[s][f]=dis;
		w[f][s]=dis;
	}
	int mi=INF,*p,mip,cur;
	for (int i=0;i<n;++i)
	{
		vh=i;
		dijkstra();
		cur=*(max_element(d,d+n));
		if(cur<mi)
		{
			mi=cur;
			mip=i;
		}
	}
	cout<<mip<<endl;
	return 0;
}

void dijkstra()
{
	memset(v,0,sizeof(v));
	memset(father,-1,sizeof(father));
	for (int i=0;i<n;++i) d[i]=(i==vh?0:INF);
	for (int i=0;i<n;++i)
	{
		int maxx,maxval=INF;
		for (int j=n-1;j>=0;--j)
		{
			if(!v[j]&&d[j]<=maxval)
			{
				maxx=j;
				maxval=d[maxx];
			}
		}
		v[maxx]=1;
		for (int j=n-1;j>=0;--j)
		{
			if(d[maxx]+w[maxx][j]<d[j])
			{
				d[j]=d[maxx]+w[maxx][j];
				father[j]=maxx;
			}
		}
	}
}