S-L14 最短路¶

#include <bits/stdc++.h>
using namespace std;

const int64_t INF = numeric_limits<int64_t>::max() / 2;

// 堆优化 Dijkstra：非负权单源最短路，O((n + m) log n)
// n: 点数（0 ~ n-1），g: 邻接表 {to, w}，s: 源点
vector<int64_t> dijkstra(int n, const vector<vector<pair<int, int>>>& g, int s) {
    vector<int64_t> dist(n, INF);
    priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;         // 过期状态，跳过
        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

#include <bits/stdc++.h>
using namespace std;

const int64_t INF = numeric_limits<int64_t>::max() / 2;

// Floyd-Warshall：多源最短路，可处理负边权（不允许负环），O(n^3)
// d[i][j] = i 到 j 的最短距离；输入 INF 表示不连通，对角线 d[i][i] = 0
void floyd(int n, vector<vector<int64_t>>& d) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] < INF && d[k][j] < INF)   // 防 INF 相加溢出
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}