单源最短路径

（正权稀疏图）动态数组存图+Djikstra算法

使用优先队列优化，时间复杂度$O(Mlog(N))$

using ll = long long;
constexpr ll INF = 1e18;

vector<ll> dis(n + 1, INF);
auto dijkstra = [&](int s = 1) -> void {
    using PII = pair<ll, int>;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    
    dis[s] = 0;
    q.emplace(0, s);
    
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        
        if (d > dis[u]) continue;
        
        for (auto [v, w] : ver[u]) {
            if (dis[v] > d + w) {
                dis[v] = d + w;
                q.emplace(dis[v], v);
            }
        }
    }
};

（负权图、判负环）Bellman-ford 算法

使用结构体存边（该算法无需存图），时间复杂度$O(NM)$

using ll = long long;
constexpr ll INF = 4e18;

struct Edge {
    int u, v;
    ll w;
};

vector<Edge> ver(m);
for (int i = 0; i < m; ++i) {
    cin >> ver[i].u >> ver[i].v >> ver[i].w;
}

vector<ll> dis(n + 1, INF);
vector<bool> chk(n + 1, false);
dis[s] = 0;

for (int i = 1; i < n; ++i) {
    bool updated = false;
    for (const auto& [u, v, w] : ver) {
        if (dis[u] < INF && dis[u] + w < dis[v]) {
            dis[v] = dis[u] + w;
            updated = true;
        }
    }
    if (!updated) break;
}

for (int i = 0; i < n; ++i) {
    for (const auto& [u, v, w] : ver) {
        if (dis[u] < INF && dis[u] + w < dis[v]) {
            dis[v] = -INF;
            chk[v] = true;
        }
        if (chk[u]) chk[v] = true;
    }
}

（负权图）SPFA 算法

以 $O(KM)$ 的复杂度计算，其中 虽然为常数，但是可以通过特殊的构造退化成接近 ，需要注意被卡

using ll = long long;
constexpr ll INF = 4e18;

struct Edge {
    int to;
    ll w;
};

vector<vector<Edge>> adj(n + 1);
vector<ll> dis(n + 1, INF);
vector<int> cnt(n + 1, 0);
vector<bool> in_q(n + 1, false);

auto spfa = [&](int s = 1) -> bool {
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    in_q[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_q[u] = false;

        for (const auto& [v, w] : adj[u]) {
            if (dis[u] < INF && dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return true; // 存在可达负环
                if (!in_q[v]) {
                    q.push(v);
                    in_q[v] = true;
                }
            }
        }
    }
    return false;
};