最小路、枚举

题意：

##分析：
版子题，枚举中间点，选两个最大的。注意图并不是连通图，选择的时候不能选自己。

代码：

#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;
    }
}