板子 Dijkstra / SPFA / Floyd

3 种最短路算法。

Dijkstra（堆优化）

• 取没有访问过的堆顶

• 标记为访问过

• 松弛各边

• 将未访问过的邻点塞进堆里

struct Node {
    int d, p;
    bool operator <(const Node &x) const {
        return x.d < d;
    }
};
priority_queue<Node> q;

inline void Dijkstra() {
    for (int i = 1; i <= n; ++i)
        d[i] = INF;
    d[s] = 0;
    q.push((Node){0, s});
    while (!q.empty()) {
        Node x = q.top();
        q.pop();
        if (v[x.p])
            continue;
        v[x.p] = true;
        for (int i = head[x.p]; i; i = e[i].nxt) {
            int y = e[i].to;
            if (d[y] > d[x.p] + e[i].w) {
                d[y] = d[x.p] + e[i].w;
                if (!v[y])
                    q.push((Node){d[y], y});
            }
        }
    }
}

SPFA

• 取队头
• 标记为出队
• 松弛各边
• 将队外的邻点怼进队里，标记为入队

queue<int> q;

inline void SPFA() {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    d[s] = 0;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u], v; i; i = e[i].next) {
            v = e[i].to;
            if (d[v] > d[u] + e[i].val) {
                d[v] = d[u] + e[i].val;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

Floyd

\(k,i,j\)

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);