跑一遍 每次用最近的更新 记录过程中的最大值 注意最后判断是否能走通整个图

时间复杂度 近似o(n)把。。。反正能过

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;

int n, m, ans;
int h[N], e[N], ne[N], idx, w[N];
bool st[N];
priority_queue<pii,vector<pii>,greater<pii>> q;

bool judge()
{
    for (int i = 1; i <= n; i ++ )
    {
        if (!st[i]) return false;
    }
    return true;
}

void bfs(int u)
{

    q.push({0, u});
    dist[u] = 0;

    while (q.size())
    {

        auto t = q.top();
        q.pop();

        int d = t.first, p = t.second;

        if (st[p]) continue;
        ans = max(ans, d);
        st[p] = true;

        for (int i = h[p]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (st[j]) continue;
            q.push({d + w[i],j});
        }
    }
}

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

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    //for (int i = h[1]; i != -1; i = ne[i]) cout << e[i] << endl;
    bfs(1);

    if (judge()) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}