记录编号	533619	评测结果	AAAWAAAA
题目名称	服务点设置	最终得分	87
用户昵称	ShallowDream雨梨	是否通过	未通过
代码语言	C++	运行时间	0.050 s
提交时间	2019-07-01 10:40:31	内存使用	14.24 MiB

#include <iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cstring>
    #include<cmath>
    using namespace std;
    struct edge{
    	int to,v,next;
    }a[50000];
    int t,dis[105],maxn[105],head[105];
    int m,n,z,x,c;//m dian,n bian
    bool vis[105];
    void add(int q,int w,int e){
    	t++;
    	a[t].next=head[q];
    	a[t].to=w;
    	a[t].v=e;
    	head[q]=t;}
    void dij(int k){
    	for(int i=0;i<m;i++)
    	dis[i]=99999999;
    	dis[k]=0;
		memset(vis,0,sizeof(vis));
    	for(int i=0;i<m;i++){
    	int qwq=-1;
    	for(int j=0;j<m;j++){
    	if(vis[j]==0&&(dis[qwq]>dis[j]||qwq==-1))
    	qwq=j;}
    	vis[qwq]=1;
		for(int j=head[qwq];j!=0;j=a[j].next)
    	dis[a[j].to]=min(dis[a[j].to],dis[qwq]+a[j].v);}}
    	
    int main(){
    	freopen("djsa.in","r",stdin);
    	freopen("djsa.out","w",stdout);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
    cin>>z>>x>>c;
    add(z,x,c);
	add(x,z,c);
	}
    for(int i=0;i<m;i++){
    dij(i);
    for(int j=0;j<m;j++){
	maxn[i]=max(dis[j],maxn[i]);
    }}
    int k=0,kk=99999999;
    cout<<endl;
    for(int o=0;o<m;o++){
    if(kk>maxn[o]){kk=maxn[o];k=o;}}
    cout<<k<<endl;

    return 0;
	}