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

#include <stdio.h>
#include <memory.h>
int a[110][110],x,y,z,i,n,m,b[110],min,minx,j,k,t1,t2;
int main()
{
	freopen("djsb.in","r",stdin);
	freopen("djsb.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(a,0x3f3f3f3f,sizeof(a));
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=a[y][x]=z;
	}
	for(i=0;i<n;i++)
		a[i][i]=0;
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=i;j<n;j++)
				if(a[i][k]+a[k][j]<a[i][j])
					a[i][j]=a[j][i]=a[i][k]+a[k][j];
	minx=0x7f7f7f7f;
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++)
		{
			memset(b,0,sizeof(b));
			min=0;
			for(k=0;k<n;k++)
			{
				if(a[i][k]<a[j][k])
					b[k]=a[i][k];
				else b[k]=a[j][k];
				if(b[k]>min)
					min=b[k];
			}
			if(min<minx)
			{
				minx=min;
				t1=i;
				t2=j;
			}
		}
	printf("%d %d",t1,t2);		
	
	return 0;
}