本题思路来源:AC大佬代码。
思路:
枚举中转点,那么最长的路就是以中转点为起点的最短路中最长的两条的和。
#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; }