题解 | #旅行#

#include <bits/stdc++.h>

using namespace std;

#define ll long long

typedef pair<int, int> pii;

const int mod = 1e4;
const int N = 1009;

int n, m;

int head[N], to[2 * N], wi[2 * N], nex[2 * N], tot;
void add(int x, int y, int w) {
    tot ++; nex[tot] = head[x]; head[x] = tot;  /// 下标从 1 开始。
    to[tot] = y;  wi[tot] = w;
}

priority_queue<pii> pq;
int vis[N], cost[N];
int dij(int h) {
    memset(vis, 0, sizeof(vis));
    memset(cost, 0x3f, sizeof(cost));
    cost[h] = 0;
    pq.push({0, h});
    int max1 = 0, max2 = 0, x;
    while(!pq.empty()){
        x = pq.top().second;  pq.pop();
        if(vis[x] ++) continue;
        max2 = max(max2, cost[x]);
        if(max1 < max2) swap(max1, max2);
        for(int i = head[x], p; i; i = nex[i]) {
            p = to[i];
            if(vis[p] || wi[i] + cost[x] >= cost[p]) continue;
            cost[p] = cost[x] + wi[i];
            pq.push({-cost[p], p});  /// 用大根堆，故存储相反数
        }
    }
    if(max2 == 0) return -1;  /// 找不到两个长度不为零的点
    return max1 + max2;
}

int main(){
    int t;  cin >> t;
    while(t --) {
        memset(head, 0, sizeof(head));  tot = 0;
        cin >> n >> m;
        int x, y, w;
        for(int i = 0; i < m; i ++) {
            cin >> x >> y >> w;
            add(x, y, w);  add(y, x, w);
        }
        int ans = -1;
        for(int i = 1; i <= n; i ++) {   /// 枚举中转点
            ans = max(ans, dij(i));
        }
        cout << ans << endl;
    }
    return 0;
}