记录编号	335736	评测结果	AAAAAAAA
题目名称	服务点设置	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	0.014 s
提交时间	2016-11-02 17:31:36	内存使用	0.34 MiB

#include <stdio.h>
#define max 0x7f7f7f7f
int a[110][110],dis[110],n,m,i,j,x,y,z,book[110],min,k,l,minx,t,i1,u;
int main()
{
	freopen("djsa.in","r",stdin);
	freopen("djsa.out","w",stdout);
	memset(a,0x7f7f7f7f,sizeof(a));
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
		a[i][i]=0;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z;
		a[y][x]=z;
	}
	minx=max;
	for(i=0;i<n;i++)
	{
		memset(book,0,sizeof(book));
		for(j=0;j<n;j++)
			dis[j]=a[i][j];
		book[i]=1;
		for(i1=0;i1<n;i1++)
		{
            min=max;			
			for(k=0;k<n;k++)
		    {
				if(book[k]==0&&dis[k]<min)
			    {
					min=dis[k];
				    u=k;
			    }
		    }
		    book[u]=1;
		    for(l=0;l<n;l++)
			    if((a[u][l]<max)&&(dis[l]>a[u][l]+dis[u]))
					dis[l]=a[u][l]+dis[u];
		}

		if(dis[u]<minx)
		{
			minx=dis[u];
			t=i;
		}
	}
	printf("%d",t);
	return 0;
}