最短路相关

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

const i64 INF = 1e18;

// Floyd算法：全源最短路径
vector<vector<i64> > floyd(int n, const vector<vector<pair<int, i64> > > &edge) {
    // 初始化距离矩阵
    vector<vector<i64> > dist(n + 1, vector<i64>(n + 1, INF));
    // 对角线设为0，处理直接边
    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
        for (const auto &e: edge[i]) {
            int v = e.first;
            i64 w = e.second;
            dist[i][v] = min(dist[i][v], w); // 处理重边
        }
    }
    // Floyd核心算法
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    return dist;
}

// SPFA算法：单源最短路径（可处理负权边）
pair<bool, vector<i64> > spfa(int s, int n, const vector<vector<pair<int, i64> > > &edge) {
    vector<i64> dist(n + 1, INF);
    vector<int> count(n + 1, 0); // 入队次数计数
    vector<bool> in_queue(n + 1, false); // 是否在队列中
    queue<int> q;
    // 初始化源点
    dist[s] = 0;
    q.push(s);
    in_queue[s] = true;
    count[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        for (const auto &e: edge[u]) {
            int v = e.first;
            i64 w = e.second;
            // 松弛操作
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                // 检查负权环
                if (++count[v] > n) {
                    return {false, dist}; // 存在负权环
                }
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return {true, dist}; // 不存在负权环
}

// Bellman-Ford 算法（双数组实现）
pair<bool, vector<i64>> bellman(int s, int n, const vector<vector<pair<int, i64>>> &edge) {
    vector<i64> dist_prev(n + 1, INF);  // 上一轮的距离数组
    vector<i64> dist_curr(n + 1, INF);  // 当前轮的距离数组
    dist_prev[s] = 0;

    // 进行 n-1 次松弛操作
    for (int i = 1; i < n; i++) {
        dist_curr = dist_prev;  // 初始化为上一轮的结果

        bool updated = false;
        for (int u = 1; u <= n; u++) {
            if (dist_prev[u] == INF) continue;
            for (const auto &e : edge[u]) {
                int v = e.first;
                i64 w = e.second;
                if (dist_prev[u] + w < dist_curr[v]) {
                    dist_curr[v] = dist_prev[u] + w;
                    updated = true;
                }
            }
        }

        // 如果没有更新，提前退出
        if (!updated) break;

        swap(dist_prev, dist_curr);  // 交换数组，准备下一轮
    }

    // 检查负权环（使用 dist_prev 作为最终结果）
    for (int u = 1; u <= n; u++) {
        if (dist_prev[u] == INF) continue;
        for (const auto &e : edge[u]) {
            int v = e.first;
            i64 w = e.second;
            if (dist_prev[u] + w < dist_prev[v]) {
                return {false, dist_prev};  // 存在负权环
            }
        }
    }

    return {true, dist_prev};  // 不存在负权环
}


// Dijkstra算法：单源最短路径（仅限非负权图）
vector<i64> dijkstra(int s, int n, const vector<vector<pair<int, i64> > > &edge) {
    vector<i64> dist(n + 1, INF);
    vector<bool> visited(n + 1, false);
    priority_queue<pair<i64, int>, vector<pair<i64, int> >, greater<> > pq;
    // 初始化源点
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (const auto &e: edge[u]) {
            int v = e.first;
            i64 w = e.second;
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

 
    return 0;
}