算法竞赛模板整理

图论

最短路

struct SPFA {
    vector<i64> dis;
    vector<bool> vis;
    vector<int> from;
    int n;
    SPFA(vector<vector<pair<int, i64>>> &g, int s) : n(g.size()) {
        dis.assign(n, INF), vis.assign(n, false), from.assign(n, -1);

        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
        q.push({0, s}), dis[s] = 0;
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            if (vis[u]) continue;
            vis[u] = true;
            for (auto &[v, w] : g[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    from[v] = u;
                    q.push({dis[v], v});
                }
            }
        }
    }
};