$O(n^2)$ 的 dijkstra

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 200000;
const int INF = 2147483647; // 此时 INF+INF < INF
int n, m, s;
int dis[MAXN + 5];  // 当前最短路
bool vis[MAXN + 5]; // 是否确定了最短路
// e[u] 存所有以 u 为起点的边：<终点, 权值>
vector<pair<int, int>> e[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    s = 1;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }

    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[s] = 0;
    for (int t = 1; t <= n; t++)
    {
        // 找到当前最近的且未确定的点 u
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == -1 || dis[i] < dis[u]))
                u = i;
        // u 点的最短路可以确定了
        if (dis[u] == INF)
            break;
        vis[u] = true;
        // 更新 u 的相邻点
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            dis[v] = min(dis[v], dis[u] + w);
        }
    }
    // 找 dis 最远的
    int ans = -1;
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] > ans)
            ans = dis[i];
        if (!vis[i])
        {
            ans = -1;
            break;
        }
    }
    cout << ans;
    return 0;
}

$O(m\log{m})$ 且使用结构体的 Dijkstra

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100'000;
const int MAXM = 200'000;
int n, m, s; // 点数、边数、出发点编号
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN + 5];
int dis[MAXN + 5];  // dis[i]: s->i 的最短路
bool vis[MAXN + 5]; // vis[i]: i 号点是否已经确定了

struct Point
{
    int id, dis;
};
bool operator<(const Point &x, const Point &y)
{
    return x.dis > y.dis;
}
priority_queue<Point> q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> m;
    s = 1;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    // dijkstra
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    q.push((Point){s, 0});
    for (int t = 1; t <= n - 1; t++)
    {
        // 找到当前距离最近且未确定的点
        while (!q.empty() && vis[q.top().id])
            q.pop();
        if (q.empty())
            break;
        int u = q.top().id;
        // u可以确定距离为 dis[u] 了
        vis[u] = true;
        // 用 u 优化其他点
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (vis[v])
                continue;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                q.push((Point){v, dis[v]});
            }
        }
    }

    // 输出
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f)
        {
            cout << -1 << " ";
            return 0;
        }
        else
            ans = max(ans, dis[i]);
    }
    cout << ans << "\n";
    return 0;
}