记录编号	581119	评测结果	AAAAAAAA
题目名称	服务点设置	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2023-07-29 14:27:30	内存使用	2.70 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef pair<int,int>P; 
const int N = 1010,M = 100010;
int n,m,ans = INT_MAX,ss;
int tot,hd[N],ver[M],ed[M],nx[M];
int dj[N][N],d[N];
bool v[N];
int add_(int x,int y,int z){
    tot++;
    ver[tot] = y,ed[tot] = z,nx[tot] = hd[x],hd[x] = tot;
}//建图 
void dij(int x){
    priority_queue<P,vector<P>,greater<P> >q;
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));
    d[x] = 0;
    q.push(make_pair(d[x],x));
    while(!q.empty()){
        int x = q.top().second;q.pop();
        if(v[x])continue;
        v[x] = 1;
        for(int i = hd[x];i;i = nx[i]){
            int y = ver[i],z = ed[i];
            if(d[x] + z < d[y]){
                d[y] = d[x] + z;
                q.push(make_pair(d[y],y));
            }
        }
    }
}//dijkstra寻找以x为起点的最短路 
bool find(int x,int y,int z){
    for(int i = hd[x];i;i = nx[i]){
        if(ver[i] == y){
            ed[i] = z;
            return 1;
        }
    }
    return 0;
}//如果有重边，以最新输入的为准
void init(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;//以0至n-1为编号改为1至n 
        if(find(x,y,z));
        else add_(x,y,z);
        if(find(y,x,z));
        else add_(y,x,z);
    }
}//输入和判断重边，如果有重边，以最新输入的为准 
void work1(){
    for(int i = 1;i <= n;i++){
        dij(i);
        for(int j = 1;j <= n;j++){
            dj[i][j] = d[j];
        }
    }
}
void pr1(){
    int s = 0;
    for(int i = 1;i <= n;i++){
        s = 0;
        for(int j = 1;j <= n;j++)
            s = max(s,dj[i][j]);
        if(s < ans){
            ans = s;ss = i;
        } 
    }//需要最大值最小的i，即服务点 
    printf("%d\n",ss-1);//因为改了下标，需要减1 
}
int main(){
    freopen("djsa.in","r",stdin);
    freopen("djsa.out","w",stdout);
    init();
    work1();
    pr1();
    
    return 0;
    
}