B-旅行
B-旅行
https://ac.nowcoder.com/acm/problem/14550
最小路、枚举
题意:
##分析:
版子题,枚举中间点,选两个最大的。注意图并不是连通图,选择的时候不能选自己。
代码:
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<functional> using namespace std; typedef long long ll; struct edge { int to, cost; }; typedef pair<int, int> pii; const int max_n = 1100; const int inf = 1e8; int n, m; int d[max_n]; vector<edge> G[max_n]; void dijstra(int s) { fill(d + 1, d + 1 + n, inf); priority_queue<pii, vector<pii>, greater<pii>> que; d[s] = 0;que.push({ d[s],s }); while (!que.empty()) { pii p = que.top();que.pop(); if (p.first > d[p.second])continue; for (int i = 0;i < G[p.second].size();i++) { int son = G[p.second][i].to; if (d[son] > d[p.second] + G[p.second][i].cost) { d[son] = d[p.second] + G[p.second][i].cost; que.push({ d[son],son }); } } } } int main() { ios::sync_with_stdio(0); int t;cin >> t; while (t--) { cin >> n >> m; for (int i = 1;i <= n;i++)G[i].clear(); for (int i = 1;i <= m;i++) { int a, b, c;cin >> a >> b >> c; G[a].push_back({ b,c }); G[b].push_back({ a,c }); } int ans = -1; for (int i = 1;i <= n;i++) { dijstra(i);int res = 0;int flag = 0;d[i] = inf; sort(d + 1, d + 1 + n, greater<int>()); for (int j = 1;j <= n;j++) { if (d[j] != inf) { res += d[j]; flag++; } if (flag == 2)break; }if (flag == 2)ans = max(ans, res); }cout << ans << endl; } }