题解 | #旅行#

思路

枚举中转点，当中转点为 i 时对应得到：res_i = f[i][0] + f[i][1]
那么最终的答案 res = max(-1，res_1，res_2，res_3，...... ，res_n)
f[i][0]：点 i 可到达的最远点(记其为x) 与点 i 之间的 距离
f[i][1]：点 i 可到达的次最远点(除 x 外，距离 i 最远的点，记其为 y) 与点 i之间 的距离
注：f[i][0] 与 f[i][1] 可能相等，但 x、y、i 三个点不能重复
若 i 找不到 对应的两个点 x、y , 则令 f[i][0] = f[i][1] =-1，以便不影响最终的结果

所以我们的思路是这样的：先预处理 求得 f 数组，再枚举中转点 得到最终结果：res

关于求 f 数组：对每个点（作为起点），使用一遍 堆优化 dijkstra

综上，Code 如下：

Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1010,M = 2*N ;

bool st[N];
int dist[N];
int f[N][2];
int h[N],e[M],ne[M],w[M],idx;
int n,m;

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(int u){
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    dist[u]=0;

    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0,u});

    while(q.size()){
        auto t=q.top();
        q.pop();
        int id=t.second,distance=t.first;

        if(st[id]) continue;

        st[id]=true;
        for(int i=h[id];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>distance+w[i]){
                dist[j]=distance+w[i];
                q.push({dist[j],j});
            }
        }
    }

    int k=0;
    sort(dist+1,dist+1+n);
    for(int i=n;i>=1;i--) if(dist[i]!=0x3f3f3f3f) {
        f[u][k++]=dist[i]; if(k==2) break;
    }

    // u做不了中转点时，令f[u][0]=f[u][1]=-1
    if(k!=2||f[u][0]==0||f[u][1]==0) f[u][0]=f[u][1]=-1;  
}


int main(){
    int T;
    cin>>T;

    while(T--){
        memset(h,-1,sizeof h);
        memset(f,0,sizeof f);
        for(int i=0;i<M;i++) e[i]=ne[i]=w[i]=0; idx=0;

        cin>>n>>m;
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c);
        }

        int maxm=-1;
        for(int i=1;i<=n;i++) dijkstra(i); 
        for(int i=1;i<=n;i++)   maxm=max(maxm,f[i][0]+f[i][1]); 

        cout<<maxm<<endl;
    }

    return 0;
}