最短路问题（一）

最短路径算法

SPFA

SPFA 算法是基于 $\text{Bellman-ford}$ 方程，具体算法描述如下
$\textbf{for} \ i = 1 \ \textbf{to} \ |G.V|-1$
$\quad \textbf{for} \ \text{each edge}(u, v) \in G.E: \quad \text{Relax}(u, v, w)$
$\textbf{for} \text{ each edge}(u, v) \in G.E$
$\quad \textbf{if} \ v.d > u.d + w(u, v): \quad \text{return FALSE}$
$\text{return TRUE}$

证明，定义最短路径权重 路径 $p = [v_0, v_1, \cdots, v_k]$，$w(p) = \displaystyle \sum_{i=1}^{k} w(v_{i-1}, v_i)$

$$\delta(u, v) = \begin{cases} \min \{w(p): u \xrightarrow{p} v \} && \text{如果存在一条从 u 到 v 的路径} \\ +\infty \end{cases}$$

结论，$\text{bellman-ford}$ 算法返回 $\text{TRUE}$ 当且仅当图 $G$ 中不包含负权重的环路

对于 $(u, v) \in E, \quad \delta(s, v) \leqslant \delta(s, u) + w(u, v), s$ 为源点

• $\text{bellman-ford}$ 算法如果能正确终止，对于 $\forall (u, v) \in E$，我们有

  $$v.d = \delta(s, v) \leqslant \delta(s, u) + w(u, v) = u.d + w(u, v)$$

• 现在假定图 $G$ 包含一个权重为负的环路，并且该环路可以从源点 $s$ 到达，不妨设环路为
  $c=\langle v_0, v_1, \cdots , v_k \rangle$，其中 $v_0 = v_k$，那么

  $$\sum_{i=1}^{k} w(v_{i-1}, v_i) < 0$$

  假设环路存在的情况下，$\text{bellman-ford}$ 返回的是 $\text{TRUE}$，那么此时 $v_{i}.d \leqslant v_{i-1}.d + w(v_{i-1}, v_i)$
  $i = 1, 2, \cdots , k$，将环路上的不等式求和，我们有

  $$\sum_{i=1}^{k} v_i.d \leqslant \sum_{k=1}^{k} (v_{i-1}.d + w(v_{i-1}, v_i)) = \sum_{i=1}^{k} v_{i-1}.d + \sum_{i=1}^{k} w(v_{i-1}, v_i)$$

  注意到 $v_0 = v_k$，所以有

  $$\sum_{i=1}^{k} v_i.d = \sum_{i=1}^{k} v_{i-1}.d$$

  从而 $0 \leqslant \displaystyle \sum_{k=1}^{k}w(v_{i-1}, v_i)$，导出矛盾

SPFA算法实现，思想是一个点可能出队，入队多次
需要用一个 $\textbf{inq}[\cdots]$ 数组判断点是否在队列中
如果判定负环的话，还需要一个 $\text{cnt}$ 数组，$\text{cnt}(x)$ 表示从 $\delta(s, x)$ 最短路径的边数
$\text{cnt}(s) = 0$
更新 $d(y) \leftarrow d(x) + z$ 时，同时更新 $\text{cnt}(y) = \text{cnt}(x) + 1$
如果发现 $\text{cnt}(y) \geqslant n$，图中有负环

分层图解决有后效性 dp

Telephone Lines

利用动态规划的思想，$dp(x, p)$ 表示从 $1 \to x$，指定 $p$ 条电缆免费，此时所需的最小花费

• $(x, y)$ 不免费，$dp(y, p) = \min(dp(y, p), \max(dp(x, p), z))$，其中 $z = w(x, y)$
• $(x, y)$ 免费，$dp(y, p+1) = dp(x, p)$

观察状态转移方程发现，存在转移
$dp(x, p) \xrightarrow{z} dp(y, p), \ dp(x, p) \to dp(y, p+1)$

如果仅有 $dp(x, p) \to dp(y, p+1)$ 的转移，直接用 $\text{dp}$ 求解是没问题的
但这里可能存在 $dp(x, p) \xrightarrow{z} dp(y, p) \to \cdots dp(y_k, p) \xrightarrow{z_k} dp(x, p)$
可能存在环路，不符合 $\text{dp}$ 状态空间转移构成有向无环图的条件

但可以利用 $\text{spfa}$，将二元组哈希成一个点
$(x, p), (y, p)$ 连长度为 $z$ 的边，$(x, p), (y, p+1)$ 连一条长度为 $0$ 的边
从 $(1, 0)$ 开始执行 $\text{spfa}$，将所有点初始化成 $d(u) = \infty$
对于边 $(u, v, z)$，每次执行更新 $d(v) = \min (d(v), \max (d(u), z))$
最后 $d(n, K)$ 就是答案

const int maxn = 2e6 + 10, inf = 0x3f3f3f3f;
const int maxm = 5e6 + 10;
int n, m, K;

namespace Graph {
    int idx = 1;
    int head[maxn], ver[maxm], e[maxm], ne[maxm];

    void initG() {
        idx = 1;
        memset(head, 0, sizeof head);
    }

    void add(int a, int b, int c) {
        ver[++idx] = b, e[idx] = c, ne[idx] = head[a], head[a] = idx;
    }
}

using namespace Graph;

inline int get(int x, int y) {
    return x + n*y;
}

int d[maxn], inq[maxn];
void spfa(int s) {
    queue<int> q;
    memset(d, inf, sizeof d);
    memset(inq, 0, sizeof inq);
    d[s] = 0, inq[s] = 1;
    q.push(s);

    while (q.size()) {
        auto u = q.front(); q.pop();
        inq[u] = 0;

        for (int i = head[u]; i; i = ne[i]) {
            int v = ver[i];
            if (d[v] > max(d[u], e[i])) {
                d[v] = max(d[u], e[i]);
                if (!inq[v]) q.push(v), inq[v] = 1;
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &K);
    initG();

    while (m--) {
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);

        for (int i = 0; i <= K; i++) {
            int u = get(a, i), v = get(b, i);
            add(u, v, l), add(v, u, l);
        }
        for (int i = 0; i < K; i++) {
            add(get(a, i), get(b, i+1), 0);
            add(get(b, i), get(a, i+1), 0);
        }
    }

    spfa(get(1, 0));
    int ans = d[get(n, K)];
    if (ans == inf) puts("-1");
    else printf("%d\n", ans);
}

spfa 和 dp

spfa 的思想和 dp 有很类似的地方，dp 中的状态转移方程 $dp(y) = dp(x) + f(x, y)$
用 spfa 算法可以让转移方程收敛到最优

最优贸易

根据 $\text{dp}$ 思想，对于某个点 $y$，用 $dp(y)$ 表示从 $1 \to y$ 路径上经过权值最小的点
$dp(y)$ 必然是从 $y$ 的前驱节点转移过来的，前驱节点集合不妨记为 $\pi (y)$

$$dp(y) = \min(dp(y), \min_{x \in \pi(y)}(dp(x), cost(y)))$$

这样对于任意节点 $u$，$dp(u)$ 即可知道 $1\to u$ 路径中最小花费的城市所需的代价
接下来只要求出 $u \to n$ 路径中最大花费的城市即可

思路是类似的，建一张从 $n \to 1$ 的反图，执行 $\text{spfa}(n)$，转移方程为

$dp2(y) = \max(dp2(y), \displaystyle \max_{x \in \pi(y)}(dp2(x), cost(y)))$

最后枚举每个节点 $u$，计算 $\max (dp2(u) - dp(u))$

add1() 表示添加正向图，add2() 表示反向图

对于单向边 (x, y)，执行 add1(x, y), add2(y, x)
如果是双向边 (x, y)，还要补上缺少的部分，add1(y, x), add2(x, y)

Dijkstra 和最短路树

$\text{Dijkstra}$ 算法可以求出最短路树，只需要 $\text{Relax}$ 操作时，只要
$d(i) + w(i, j) < d(j)$ 更新 $d(j)$ 时，同时令 $p(j) = i$，这样把 $p$ 看成是父指针，
起点的 $p(s) = s$，其他每个点对应一条边 $p(u) \to u$

$\text{dijkstra}$ 的 $\text{vis}(u)$ 数组表示 $u$ 这个节点是否被扩展过
$\text{spfa}$ 的 $\text{inq}(u)$ 表示 $u$ 是否在队列中

Warfare and Logistics

对于 $G$ 中的任意原点 $\forall s$，都可以用 $\text{dijkstra}(s)$ 求出任意节点 $i \in V$ 的最短路，记为

$\delta(s, i) = d(i)$，以 $s$ 为源点，所有点的最短路径和记为 $C(s) = \displaystyle \sum_{i = 1}^{n} d(i)$

本例令 $res = \displaystyle\sum_{s = 1}^{n} C(s)$，要求删除一条边之后，使得新的 $res'$ 最大

源点为 $s$ 的单源最短路，生成的最短路树不妨表示为前驱子图 $V_{\pi}(s)$
最短路树以 $s$ 为根，如果删除的边 $e \not\in V_{\pi}(s)$，最短路值都不会发生改变
而 $V_{\pi}(s)$ 上恰好有 $n$ 个点 $n-1$ 条边

所以只需要枚举最短路树上的边，尝试删除并重新计算最短路，取一个 $\max$ 即可

• 如果删除的边 $\forall e \not\in V_{\pi}(s)$，那么 $C(s)$ 值不变
• 否则，$e \in V_{\pi}(s)$，需要重新计算最短路 $\text{dijkstra}(s)$，并且求出新的 $C[s] = \displaystyle \sum_{i = 1}^{n} d(i)$

具体到算法实现上

1. 对每个源点 $s \in [1, n]$ 初始化 $d(i) = +\infty, p(i) = 0$ 并且 $\text{dijkstra}(s)$ 得到 $d(i), p(i)$

   $C[s] += \displaystyle\sum_{i = 1}^{n} d(i)$

   然后执行 $\text{dfs}(s)$，对 $\{(u, v): \ p(v) = u\}$ 的边标记为必须边，$\text{mark}(s, u, v) = 1$

2. 枚举最短路树上的边，其实是枚举每个点对 $(i, j)$
   对于边 $(i, j)$，枚举每个顶点 $s$，如果 $(i, j)$ 是 $V_{\pi}(s)$ 的树边，将 $w(i, j) = 0$
   重新计算 $\text{dijkstra}(s)$，并且将结果 $res += \sum d(i)$，否则的话直接 $res += C[s]$
   计算完之后记得还原现场，对 $res$ 求一个 $\max$ 即可

const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10, maxm = 2000 + 10;
int n, m, L;
vector<int> edges[maxn][maxn];
int ID[maxn][maxn];
typedef pair<int, int> PII;

namespace Graph {
    int idx = 1;
    int head[maxn], ver[maxm], ne[maxm], e[maxm];
    void initG() {
        idx = 1;
        memset(head, 0, sizeof head);
        memset(ID, 0, sizeof ID);
        _for(i, 0, maxn) _for(j, 0, maxn) edges[i][j].clear();
    }

    void add(int a, int b, int c) {
        ver[++idx] = b, e[idx] = c, ne[idx] = head[a], head[a] = idx;
        ID[a][b] = idx;
    }

    int d[maxn], p[maxn], vis[maxn];
    void dijkstra(int s) {
        memset(d, inf, sizeof d);
        memset(p, 0, sizeof p);
        memset(vis, 0, sizeof vis);

        d[s] = 0;
        priority_queue<PII, vector<PII>, greater<PII> > q;
        q.push({0, s});

        while (q.size()) {
            auto u = q.top(); q.pop();
            int x = u.second;

            if (vis[x]) continue;
            vis[x] = true;

            for (int i = head[x]; i; i = ne[i]) {
                int y = ver[i];
                if (e[i] > 0 && d[y] > d[x] + e[i]) {
                    d[y] = d[x] + e[i], p[y] = x;
                    q.push({d[y], y});
                }
            }
        }
    }
}
using namespace Graph;
ll C[maxn];
int mark[maxn][maxn][maxn];

void get_mark(int s) {
    for (int i = 1; i <= n; i++) {
        if (p[i] == 0) continue;
        mark[s][i][p[i]] = mark[s][p[i]][i] = 1;
    }
}

void calc() {
    memset(C, 0, sizeof C);
    memset(mark, 0, sizeof mark);

    for (int s = 1; s <= n; s++) {
        dijkstra(s);
        get_mark(s);
        for (int i = 1; i <= n; i++) C[s] += d[i] == inf ? L : d[i];
    }

    ll sum = 0;
    for (int s = 1; s <= n; s++) sum += C[s];
    printf("%lld ", sum);
}

ll del(int i, int j) {
    ll sum = 0;
    int id = ID[i][j];

    if (edges[i][j].size() == 1) e[id] = e[id^1] = 0;
    else if (edges[i][j].size() > 1) e[id] = e[id^1] = edges[i][j][1];

    for (int s = 1; s <= n; s++) {
        if (mark[s][i][j] == 0) sum += C[s];
        else {
            dijkstra(s);
            for (int u = 1; u <= n; u++) sum += d[u] == inf ? L : d[u];
        }
    }

    e[id] = e[id^1] = edges[i][j][0];
    return sum;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d%d", &n, &m, &L) == 3) {
        initG();

        while (m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            edges[a][b].push_back(c), edges[b][a].push_back(c);
        }

        // add
        for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
            if (edges[i][j].size() == 0) continue;
            sort(edges[i][j].begin(), edges[i][j].end());

            add(i, j, edges[i][j][0]), add(j, i, edges[i][j][0]);
        }

        // calc
        calc();

        ll res = 0;
        for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
            if (edges[i][j].size() == 0) continue;
            res = max(res, del(i, j));
        }
        printf("%lld\n", res);
    }
}

dijkstra 和拓扑排序

SPFA 算法复杂度最坏可能达到 $O(nm)$，在某些特殊构造的图上会超出时限
道路与航线

对于 $\text{dijkstra}$ 算法，在非负权的连通块中，从起点 $s$ 总能找到一条最短路
注意到本例中只有航线是负权，并且航线形成的路径是一个 $\text{DAG}$
由此可以设计出如下算法

一开始只加入正权边，然后这些边形成正权连通块，将连通块缩点
再加入负权边，负权边和连通块构成了新的 DAG，在 DAG 上用拓扑排序或者 dp
对于连通块，拓扑序为 $cc_1\to cc_2$，可知 $d(cc_2) = \min (d(cc_2), d(cc_1) + w(cc_1, cc_2))$
而对于连通块 $cc_1$ 而言，假设起点为 $s$，执行 $\text{dijkstra}(s)$
可以快速求出任意节点的最短路 $d(y) = \delta (s, y)$
对于横跨连通块的边界点，放入拓扑队列中，依次进行 $\text{dijkstra}$ 松弛，最后 $d$ 数组就是答案

具体来说

1. 只加入正权边，然后对所有点 $\forall \ x \in G$ 执行 $\text{dfs}$ 找连通块 $[1\cdots cnt]$，得到 $c[x]$
   表示 $x$ 属于哪个连通块
2. 加入负权边 $(x, y)$，如果 $c[x] \neq c[y]$，那么 $++\text{deg}(c[y])$
3. 主算法执行拓扑序 dp，用队列 $q$ 维护连通块拓扑序
   • 找到 $\text{deg}[cc] = 0$ 的连通块 $cc$，入队列 $q[\cdots] \leftarrow cc$，不要忘了初始化 $d$ 数组
     $d[\cdots] = \infty, \ d(S) = 0$
   • $\textbf{while} \ q[\cdots] \neq \emptyset: \quad cc \leftarrow q.\text{front}()$
     扫描所有的点 $\forall u \in V$，对于 $c[u] = cc$ 的点，插入 $\text{heap}$ 堆
     $\textbf{while} \ \text{heap} \neq \emptyset$，执行堆优化的 $\text{dijkstra}$
     注意这里对每个连通块局部进行 $\text{dijkstra}$，检查每条边 $(x, y)$
     只对正权边使用 $\text{dijkstra}$，堆只维护 $c[x] = c[y]$ 的边 $(x, y)$
     $\quad d(y) < d(x) + e(x, y)$ 的时候，更新 $d(y)$，仅 $c[x] = c[y]$ 时 $y$ 入堆
   • 检查 $(x, y): \ c[x] \neq c[y] \ \textbf{and} \ --\text{deg}(c[y]) = 0$，将 $q[\cdots] \leftarrow c[y]$ 入队列
     此时 $c[y]$ 作为下个拓扑序连通块

typedef pair<int, int> PII;
const int maxn = 25000 + 10, inf = 0x3f3f3f3f;
const int maxm = 2e5 + 10;

int n, R, P, S;

namespace Graph {
    int idx = 1, cnt = 0;
    int head[maxn], ver[maxm], e[maxm], ne[maxm], C[maxn], deg[maxn];

    void initG() {
        idx = 1;
        cnt = 0;
        memset(head, 0, sizeof head);
        memset(C, 0, sizeof C);
        memset(deg, 0, sizeof deg);
    }

    void add(int a, int b, int c) {
        ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
    }

    void dfs(int u) {
        C[u] = cnt;
        for (int i = head[u]; i; i = ne[i]) {
            int v = ver[i];
            if (C[v]) continue;
            dfs(v);
        }
    }

    void dfs() {
        for (int i = 1; i <= n; i++) {
            if (!C[i]) {
                ++cnt;
                dfs(i);
            }
        }
    }
}

using namespace Graph;

int d[maxn], vis[maxn];
void solve() {
    memset(d, inf, sizeof d);
    memset(vis, 0, sizeof vis);
    d[S] = 0;
    
    queue<int> q;
    for (int i = 1; i <= cnt; i++) if (deg[i] == 0) q.push(i);

    while (q.size()) {
        auto cc = q.front(); q.pop();
        
        priority_queue<PII, vector<PII>, greater<PII> > heap;
        for (int i = 1; i <= n; i++) if (C[i] == cc) heap.push({d[i], i});

        while (heap.size()) {
            int x = heap.top().second; heap.pop();
            if (vis[x]) continue;
            vis[x] = true;

            for (int i = head[x]; i; i = ne[i]) {
                int y = ver[i];
                if (C[y] != C[x] && --deg[C[y]] == 0) q.push(C[y]);
                if (d[y] > d[x] + e[i]) {
                    d[y] = d[x] + e[i];
                    if (C[x] == C[y]) heap.push({d[y], y});
                }
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> R >> P >> S;
    initG();

    // add + 
    while (R--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    // dfs
    dfs();

    // add -
    while (P--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        if (C[a] != C[b]) ++deg[C[b]];
    }

    // solve
    solve();

    for (int i = 1; i <= n; i++) {
        if (d[i] >= 1e9) puts("NO PATH");
        else printf("%d\n", d[i]);
    }
}