题目描述

题目描述 小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。 小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。 然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。 你能帮帮小z吗？ 需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.

解题思路：

这是对题目提取的重要信息：

1. 首先小z只能在三个只能在三个旅行景点进行游玩
2. 每次从一个点走到另外一个点的时候都走最短路径
3. 想选择的路程尽量长

因为不知道起点是什么，所以每个点都是起点， 从原点出发找最短路，我们定义两个变量，第一个变量为某个点到原点最大值。第二个是第二大的值，然后将两个值相加，也就是三个点最大路径。 然后将这些不同起点到某个点的答案进行比较

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int>PII;

const int N = 1e5 + 10;
int h[N], ne[N], e[N], idx, w[N];

int dist[N];
bool st[N];

int t, n, m;


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

int dj (int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});
    
    int ans1 = 0; int ans2 = 0;
    
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        
        if (st[ver]) continue;
        st[ver] = true;
        
        ans2 = max(ans2, dist[ver]);
        if (ans2 > ans1) swap(ans2, ans1);
        
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (ans2 == 0) return -1;
    return ans1 + ans2;
}


int main(){
    cin >> t;
    while (t--) {
        memset(h, -1, sizeof h);
        cin >> n >> m;
        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
            add(b, a, c);
        }
        int ans = -1;
        for (int i = 1; i <= n; i++) ans = max(ans, dj(i));
        cout << ans << endl;
    }
    return 0;
}