记录编号	251712	评测结果	AAAAAAAA
题目名称	双服务点设置	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-18 15:31:39	内存使用	0.06 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=110;
const int maxe=maxn*maxn;
struct Edge
{
	int to,dis,next;
};
struct Node
{
	int num;
	int dis;
	Node(){	};
	Node(int a,int b){num=a;dis=b;}
	bool operator <(const Node & a)const
	{
		return dis>a.dis;
	}
};
Edge e[maxe];
int n,m,head[maxn],len=0,d[maxn][maxn];
void Init();
void Dijs(int);
void Insert(int,int,int);
int Min(int ,int);
int PT(){
	freopen("djsb.in","r",stdin);
	freopen("djsb.out","w",stdout);
	Init();
	return 0;
}
int PS=PT();
int main(){;}
void Init()
{
	memset(head,-1,sizeof(head));
	memset(d,-1,sizeof(d));
	memset(e,0,sizeof(e));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);
		Insert(y,x,z);
	}
	for(int i=0;i<n;i++)
	{
	    Dijs(i);
	}
	int _min=0x7f7f7f7f,k1,k2;
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int _max=0;
			for(int k=0;k<n;k++)
			{
				int x=Min(d[k][i],d[k][j]);
				if(_max<x)_max=x;
			}
			if(_max<_min)
			{
				_min=_max;
				k1=i;k2=j;
			}	
		}
	}
	cout<<k1<<" "<<k2<<endl; 
}
void Insert(int x,int y,int z)
{
	len++;
	e[len].to=y;
	e[len].next=head[x];
	e[len].dis=z;
	head[x]=len;
}
void Dijs(int x)
{
	int dis[maxn];
	priority_queue<Node> q;
	memset(dis,0x7f,sizeof(dis));
	bool f[maxn]={0};
	f[x]=1;dis[x]=0;
	q.push(Node(x,dis[x]));
	while(!q.empty())
	{
		Node temp=q.top();
		q.pop();
		int k=temp.num;
		f[k]=1;
		for(int i=head[k];i!=-1;i=e[i].next)
		{
			int j=e[i].to;
			if(!f[j] && dis[j]>dis[k]+e[i].dis)
			{
				dis[j]=dis[k]+e[i].dis;
				q.push(Node(j,dis[j]));
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		d[x][i]=dis[i];
	}
}
int Min(int x,int y)
{
	if(x>=y)return y;
	if(x<=y)return x;
}