记录编号	125225	评测结果	AAAAAAAA
题目名称	双服务点设置	最终得分	100
用户昵称	窝	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-10-08 06:29:35	内存使用	0.39 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,x,y,v;
int dis[101][101];
int maxx[101][101];
int main()
{
	
	freopen("djsb.in","r",stdin);
	freopen("djsb.out","w",stdout);
     cin>>n>>m;
for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
  {
  	dis[i][j]=0x7f;
  	maxx[i][j]=0;
  }
	
	for(int i=0;i<n;i++)
	   dis[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		cin>>dis[x][y];
		dis[y][x]=dis[x][y];
	}
	for(int k=0;k<n;k++)
	  for(int i=0;i<n;i++)
	   for(int j=0;j<n;j++)
	    {
	    	if(dis[i][j]>dis[i][k]+dis[k][j] )
	           dis[i][j]=dis[i][k]+dis[k][j];
	}
	int w[101][101],c;
	  for(int i=0;i<n;i++)
	   for(int j=i+1;j<n;j++)
	   {	for(int k=0;k<n;k++)
	          {
	          	   if(k!=i&& i!=j && k!=j)
	          	    {
	          	      	if(dis[i][k]<dis[j][k])
	          	      	  c=dis[i][k];
	          	      	else  c=dis[j][k]; 
	                   if(c>maxx[i][j])
	                   {
	                    	maxx[i][j]=c;
	                   }
	          	   }
	          	
	         }
	   	   w[i][j]=maxx[i][j];
	   }
	int minn=0x7f,k1,k2;
	for(int i=0;i<n;i++)
	 for(int j=i+1;j<n;j++)
	 {
	 	if(minn>w[i][j] && i!=j )
	 	{
	 		minn=w[i][j];
	 		k1=i;
	 		k2=j;
	 	}
	 }
	 cout<<k1<<' '<<k2;
	return 0;
}