记录编号	219275	评测结果	WWAWWWWW
题目名称	服务点设置	最终得分	12
用户昵称	Hzoi_	是否通过	未通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-01-13 17:46:41	内存使用	0.45 MiB

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const  int maxn=110,maxe=maxn*maxn;
struct a
{
	int to;
	int pay;
	int next;
};
a road[maxe];
int last[maxn];
int minroad[maxn];
int numberroad,numbervillage,numberlen=0;

void cinn();
int findfor(int);
void give(int,int,int);

int main()
{
	freopen("djsa.in","r",stdin);	
	freopen("djsa.out","w",stdout);	
	int minw=0x7f7f7f7f,miw; 
	cinn();
	for(int i=0;i<numbervillage;i++)minroad[i]=findfor(i);
	int maxc=0x7f7f7f7f,mia;
	for(int i=0;i<numbervillage;i++)
	{
		if(maxc>minroad[i])
		maxc=minroad[i];
		mia=i;
	}
	cout<<mia;
}

void cinn()
{
	memset(minroad,0,sizeof(minroad));
	memset(road,0,sizeof(road));
	memset(last,-1,sizeof(last));

	scanf("%d%d",&numbervillage,&numberroad);
	for(int i=1;i<=numberroad;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		give(x,y,z);
		give(y,x,z);
	}
}

void give(int x,int y,int z)
{
	numberlen+=1;
	road[numberlen].to=y;
	road[numberlen].pay=z;
	road[numberlen].next=last[x];
	last[x]=numberlen;
}

int findfor(int start)
{
	bool flag[maxn];
	int dis[maxn];
	memset(flag,0,sizeof(flag));
	flag[start]=1;
	memset(dis,0x7f,sizeof(dis));
	dis[start]=0;
	for(int i=last[start];i!=-1;i=road[i].next)
	{
		int k=road[i].to;
		dis[k]=road[i].pay;
	}
	/*for(int i=0;i<numbervillage;i++)
	{
		cout<<"h="<<dis[i]<<endl;
	}*/
	for(int i=1;i<numbervillage;i++)
	{
		int minn=0x7f7f7f7f,k;
		for(int j=0;j<numbervillage;j++)
		{
			if(!flag[j]&&dis[j]<minn)
			{
				minn=dis[j];
				k=j;
			}
		}
		flag[k]=1;
		
		for(int j=last[k];j!=-1;j=road[j].next)
		{
			int c=road[j].to;
			if(dis[c]>dis[k]+road[c].pay)
			{
				dis[c]=dis[k]+road[c].pay;
			}
		}
	}
	
  	int maxc=0;
	for(int i=0;i<numbervillage;i++)
	{
		if(dis[i]>maxc&&dis[i]!=0x7f7f7f7f)maxc=dis[i];
	}
	return maxc;
}