第 31 章 最短路 · 知识细节练习

最短路的定义是？

判断题：图有两种基本表示——邻接矩阵（$O(n^2)$ 空间、查边 $O(1)$）与邻接表（$O(n+m)$ 空间、遍历出边快）——稠密图用矩阵、稀疏图用表。

单源最短路与多源最短路的区别是？

判断题：Dijkstra 要求边权非负；Bellman-Ford/Floyd 可处理负权（但要求无负环）。

松弛（relaxation）操作是？

判断题：最短路算法总表——Dijkstra（非负单源）、Bellman-Ford（负权单源 + 判负环）、SPFA（BF 队列优化）、Floyd（多源）。

Dijkstra 的核心思想是？

Dijkstra 的步骤是？

判断题：Dijkstra 要求所有边权非负——负权边会破坏"已确定点的 dist 不再变"的性质。

朴素 Dijkstra 与堆优化 Dijkstra 的复杂度分别是？

判断题：Dijkstra 中已确定（出队）的点，之后还有可能被松弛更新出更短的 dist。

判断题：Dijkstra 正确性直觉——当前 dist 最小的未确定点，任何绕路都不可能比它更短（边权非负），故可确定。

判断题：所有边权为 1 时，Dijkstra 退化为 BFS——dist 就是层数。

Bellman-Ford 的核心思想是？

判断题：Bellman-Ford 能处理负权边（无负环时正确）。

Bellman-Ford 判负环的方法是？

SPFA 是 Bellman-Ford 的什么优化？

SPFA 的复杂度是？

判断题：SPFA 在任何数据下都不会超时——正权图上可以完全放心使用。

判断题：Dijkstra 快但要求非负；BF/SPFA 支持负权但可能被卡——按边权性质选。

Floyd 的核心思想是？

Floyd 的三重循环顺序是？

Floyd 的复杂度是？

判断题：Floyd 一次求出所有点对的最短路——适合 $n$ 小（如 $n \le 500$）的稠密图。

判断题：Floyd 不能处理任何负权边——只要边权为负就必须改用 Bellman-Ford。

Floyd 判负环的方法是？

判断题：Floyd 可求传递闭包——把 min/+ 换成 or/and，$d[i][j]$ 表示 i 能否到达 j。

次短路的定义是？

次短路的求法是？

分层图思想是？

判断题：最短路变体——路径计数、字典序最小路径、经过指定点——都在 Dijkstra 上加额外状态。

判断题：特殊最短路（如 2025 真题"至多免费一条边"）= 分层图——免费次数作为层维度。

判断题：次短路与分层图是 S 组完善程序的高频变体——核心都是"扩展状态"。

判断题：实际问题（换乘最少/费用最低/传递消息）建模成最短路——点是状态、边是转移、权是代价。

判断题：路径还原用 pre[v] = u 记录前驱，最后从终点倒推——Dijkstra/BF/SPFA 皆可。

判断题：最短路计数——松弛更新时继承计数、相等时累加计数。

判断题：差分约束系统（$x_i - x_j \le c$ 类不等式）可转最短路求解——建边求最短路。

判断题：Dijkstra 本质是"图上 DP"（DAG 上即拓扑序 DP）——状态是点、转移是边。

判断题：最短路是图论应用最广的算法——建模能力比算法本身更重要。

四算法总表是？

$n \le 500$ 的稠密图求所有点对最短路，选？

判断题：堆优化 Dijkstra 在任何图上都严格优于朴素 Dijkstra。

判断题：有负权边选 BF/SPFA/Floyd；有负环则最短路无意义（可无限绕圈变短）。

需要"判负环 + 单源最短路"，选？

判断题：选择流程——先看边权（负？）、再看单源还是多源、最后看 $n, m$ 规模。

判断题：负权图用 Dijkstra 会得到错误答案——"已确定"性质被破坏。

判断题：Floyd 的 k 必须在最外层——k 在内层则 DP 含义错乱、结果可能错。

判断题：SPFA 判负环 = 记录入队次数，某点入队 > n 次则有负环——忘判会死循环。

判断题：dist 初始化——起点 0、其余 INF；若 INF 取太小会被误当路径长。

判断题：以下结论全部正确——"Dijkstra 要求非负权；Floyd k 层在最外；SPFA 入队次数判负环；次短路维护两个 dist；分层图扩状态"。

01#include <bits/stdc++.h>
02using namespace std;
03const int INF = 0x3f3f3f3f;
04int main() {
05    int n = 4;
06    int w[5][5];
07    memset(w, 0x3f, sizeof w);
08    w[1][2] = 2; w[1][3] = 5; w[2][3] = 1; w[2][4] = 6; w[3][4] = 2;
09    int dist[5], vis[5] = {0};
10    for (int i = 1; i <= n; i++) dist[i] = INF;
11    dist[1] = 0;
12    for (int it = 0; it < n; it++) {
13        int u = -1;
14        for (int i = 1; i <= n; i++)
15            if (!vis[i] && (u == -1 || dist[i] < dist[u])) u = i;
16        vis[u] = 1;
17        for (int v = 1; v <= n; v++)
18            if (w[u][v] != INF && dist[v] > dist[u] + w[u][v])
19                dist[v] = dist[u] + w[u][v];
20    }
21    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
22    return 0;
23}

单选题：程序输出是？（从 1 号点出发的最短路距离）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 2});
09    int dist[5], vis[5] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    dist[1] = 0;
12    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
13    q.push({0, 1});
14    while (!q.empty()) {
15        auto [d, u] = q.top(); q.pop();
16        if (vis[u]) continue;
17        vis[u] = 1;
18        cout << u << " ";
19        for (auto [v, w] : g[u])
20            if (dist[v] > d + w) {
21                dist[v] = d + w;
22                q.push({dist[v], v});
23            }
24    }
25    return 0;
26}

单选题：程序输出是？（点被确定的最短距离顺序）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4, s = 2;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 2});
09    int dist[5], vis[5] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    dist[s] = 0;
12    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
13    q.push({0, s});
14    while (!q.empty()) {
15        auto [d, u] = q.top(); q.pop();
16        if (vis[u]) continue;
17        vis[u] = 1;
18        for (auto [v, w] : g[u])
19            if (dist[v] > d + w) {
20                dist[v] = d + w;
21                q.push({dist[v], v});
22            }
23    }
24    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
25    return 0;
26}

单选题：程序输出是？（图是有向图，从 2 号点出发）

01#include <bits/stdc++.h>
02using namespace std;
03const int INF = 0x3f3f3f3f;
04int main() {
05    int n = 4;
06    int w[5][5];
07    memset(w, 0x3f, sizeof w);
08    w[1][2] = 2; w[1][3] = 5; w[2][3] = 1; w[2][4] = 6; w[3][4] = 2;
09    int dist[5], vis[5] = {0};
10    for (int i = 1; i <= n; i++) dist[i] = INF;
11    dist[1] = 0;
12    for (int it = 0; it < n; it++) {
13        int u = -1;
14        for (int i = 1; i <= n; i++)
15            if (!vis[i] && (u == -1 || dist[i] < dist[u])) u = i;
16        vis[u] = 1;
17        for (int v = 1; v <= n; v++)
18            if (w[u][v] != INF && dist[v] > dist[u] + w[u][v])
19                dist[v] = dist[u] + w[u][v];
20        if (u == 2) {                    // 刚确定 2 号点时输出
21            for (int i = 1; i <= n; i++) cout << dist[i] << " ";
22        }
23    }
24    return 0;
25}

单选题：程序输出是？（刚确定 2 号点时的 dist 数组）

01while (!q.empty()) {
02    auto [d, u] = q.top(); q.pop();
03    if (vis[u]) continue;
04    vis[u] = 1;
05    for (auto [v, w] : g[u]) {
06        if (dist[v] > d + w) {
07            dist[v] = ______;       // 更新为更短距离
08            q.push({dist[v], v});
09        }
10    }
11}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 3});          // 注意：3->4 的边权是 3
09    int dist[5], vis[5] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    dist[1] = 0;
12    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
13    q.push({0, 1});
14    while (!q.empty()) {
15        auto [d, u] = q.top(); q.pop();
16        if (vis[u]) continue;
17        vis[u] = 1;
18        for (auto [v, w] : g[u])
19            if (dist[v] > d + w) {
20                dist[v] = d + w;
21                q.push({dist[v], v});
22            }
23    }
24    cout << dist[4];
25    return 0;
26}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Edge { int u, v, w; };
04int main() {
05    int n = 3;
06    vector<Edge> e = {{1,2,2}, {1,3,3}, {2,3,-1}};
07    int dist[4];
08    memset(dist, 0x3f, sizeof dist);
09    dist[1] = 0;
10    for (int r = 1; r <= n - 1; r++)          // 松弛 n-1 轮
11        for (auto [u, v, w] : e)
12            if (dist[v] > dist[u] + w)
13                dist[v] = dist[u] + w;
14    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
15    return 0;
16}

单选题：程序输出是？（含负权边的最短路）

01#include <bits/stdc++.h>
02using namespace std;
03struct Edge { int u, v, w; };
04int main() {
05    int n = 3;
06    vector<Edge> e = {{2,3,-1}, {1,2,2}, {1,3,3}};   // 注意边的顺序
07    int dist[4];
08    memset(dist, 0x3f, sizeof dist);
09    dist[1] = 0;
10    for (int r = 1; r <= n - 1; r++) {
11        for (auto [u, v, w] : e)
12            if (dist[v] > dist[u] + w)
13                dist[v] = dist[u] + w;
14        cout << dist[3] << " ";          // 每轮结束输出 dist[3]
15    }
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Edge { int u, v, w; };
04int main() {
05    int n = 3;
06    vector<Edge> e = {{1,2,1}, {2,3,-1}, {3,1,-1}};  // 环权值和 -1
07    int dist[4];
08    memset(dist, 0x3f, sizeof dist);
09    dist[1] = 0;
10    bool neg = false;
11    for (int r = 1; r <= n; r++) {
12        bool upd = false;
13        for (auto [u, v, w] : e)
14            if (dist[v] > dist[u] + w) {
15                dist[v] = dist[u] + w;
16                upd = true;
17            }
18        if (r == n && upd) neg = true;   // 第 n 轮仍有松弛
19    }
20    cout << (neg ? "YES" : "NO");
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    vector<pair<int,int>> g[4];
06    g[1].push_back({2, 2}); g[1].push_back({3, 3});
07    g[2].push_back({3, -1});
08    int dist[4], inq[4] = {0};
09    memset(dist, 0x3f, sizeof dist);
10    dist[1] = 0;
11    queue<int> q;
12    q.push(1); inq[1] = 1;
13    while (!q.empty()) {
14        int u = q.front(); q.pop();
15        inq[u] = 0;
16        for (auto [v, w] : g[u])
17            if (dist[v] > dist[u] + w) {
18                dist[v] = dist[u] + w;
19                if (!inq[v]) { q.push(v); inq[v] = 1; }
20            }
21    }
22    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
23    return 0;
24}

单选题：程序输出是？

01if (!inq[v]) {
02    q.push(v);
03    ______;          // 标记 v 已入队
04}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    vector<pair<int,int>> g[4];
06    g[1].push_back({2, 1});
07    g[2].push_back({3, -1});
08    g[3].push_back({1, -1});
09    int dist[4], cnt[4] = {0}, inq[4] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    dist[1] = 0;
12    queue<int> q;
13    q.push(1); inq[1] = 1;
14    while (!q.empty()) {
15        int u = q.front(); q.pop();
16        inq[u] = 0;
17        for (auto [v, w] : g[u])
18            if (dist[v] > dist[u] + w) {
19                dist[v] = dist[u] + w;
20                cnt[v] = cnt[u] + 1;
21                if (cnt[v] > n) { cout << "YES"; return 0; }
22                if (!inq[v]) { q.push(v); inq[v] = 1; }
23            }
24    }
25    cout << "NO";
26    return 0;
27}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03const int INF = 0x3f3f3f3f;
04int main() {
05    int n = 4;
06    int d[5][5];
07    memset(d, 0x3f, sizeof d);
08    for (int i = 1; i <= n; i++) d[i][i] = 0;
09    d[1][2] = 2; d[1][3] = 5; d[2][3] = 1; d[2][4] = 6; d[3][4] = 2;
10    for (int k = 1; k <= n; k++)
11        for (int i = 1; i <= n; i++)
12            for (int j = 1; j <= n; j++)
13                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
14    cout << d[1][4] << " " << d[2][4];
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    int d[5][5];
06    memset(d, 0x3f, sizeof d);
07    for (int i = 1; i <= n; i++) d[i][i] = 0;
08    d[1][2] = 2; d[1][3] = 5; d[2][3] = 1; d[2][4] = 6; d[3][4] = 2;
09    for (int k = 1; k <= n; k++) {
10        for (int i = 1; i <= n; i++)
11            for (int j = 1; j <= n; j++)
12                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
13        cout << d[1][4] << " ";       // 每层 k 结束输出 d[1][4]
14    }
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    bool r[5][5] = {};
06    r[1][2] = r[1][3] = r[2][3] = r[2][4] = r[3][4] = true;
07    for (int i = 1; i <= n; i++) r[i][i] = true;
08    for (int k = 1; k <= n; k++)
09        for (int i = 1; i <= n; i++)
10            for (int j = 1; j <= n; j++)
11                r[i][j] = r[i][j] || (r[i][k] && r[k][j]);
12    for (int j = 1; j <= n; j++) cout << r[1][j] << " ";
13    cout << endl;
14    for (int j = 1; j <= n; j++) cout << r[4][j] << " ";
15    return 0;
16}

单选题：程序输出是？（第一行 = 1 号点能否到达各点，第二行 = 4 号点能否到达各点）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    int d[4][4];
06    memset(d, 0x3f, sizeof d);
07    for (int i = 1; i <= n; i++) d[i][i] = 0;
08    d[1][2] = 1; d[2][3] = -1; d[3][1] = -1;
09    for (int k = 1; k <= n; k++)
10        for (int i = 1; i <= n; i++)
11            for (int j = 1; j <= n; j++)
12                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
13    bool neg = false;
14    for (int i = 1; i <= n; i++)
15        if (d[i][i] < 0) neg = true;
16    cout << (neg ? "YES" : "NO");
17    return 0;
18}

单选题：程序输出是？

01for (int k = 1; k <= n; k++)
02    for (int i = 1; i <= n; i++)
03        for (int j = 1; j <= n; j++)
04            d[i][j] = min(d[i][j], ______);   // 以 k 为中转点

单选题：横线处应填入？

01// 图同 K1：4 个点的有向图，求任意两点间最短路
02// 问：d[2][4] 最终的值是多少？
03int d[5][5];
04memset(d, 0x3f, sizeof d);
05for (int i = 1; i <= 4; i++) d[i][i] = 0;
06d[1][2] = 2; d[1][3] = 5; d[2][3] = 1; d[2][4] = 6; d[3][4] = 2;
07for (int k = 1; k <= 4; k++)
08    for (int i = 1; i <= 4; i++)
09        for (int j = 1; j <= 4; j++)
10            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
11cout << d[2][4];

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03const int INF = 0x3f3f3f3f;
04int main() {
05    int n = 4;
06    int d[5][5];
07    memset(d, 0x3f, sizeof d);
08    for (int i = 1; i <= n; i++) d[i][i] = 0;
09    d[1][2] = 2; d[1][3] = 5; d[2][3] = 1; d[2][4] = 6; d[3][4] = 2;
10    for (int k = 1; k <= n; k++)
11        for (int i = 1; i <= n; i++)
12            for (int j = 1; j <= n; j++)
13                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
14    for (int i = 1; i <= 2; i++) {          // 只输出前两行
15        for (int j = 1; j <= n; j++) {
16            if (d[i][j] == INF) cout << "INF"; else cout << d[i][j];
17            cout << " ";
18        }
19        cout << endl;
20    }
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03const int INF = 0x3f3f3f3f;
04int main() {
05    int n = 4;
06    vector<pair<int,int>> g[5];
07    g[1].push_back({2, 2}); g[1].push_back({3, 5});
08    g[2].push_back({3, 1}); g[2].push_back({4, 6});
09    g[3].push_back({4, 2});
10    int dist1[5], dist2[5];            // 最短路 与 次短路
11    for (int i = 1; i <= n; i++) dist1[i] = dist2[i] = INF;
12    dist1[1] = 0;
13    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
14    q.push({0, 1});
15    while (!q.empty()) {
16        auto [d, u] = q.top(); q.pop();
17        if (d > dist2[u]) continue;
18        for (auto [v, w] : g[u]) {
19            int nd = d + w;
20            if (nd < dist1[v]) {
21                dist2[v] = dist1[v];
22                dist1[v] = nd;
23                q.push({nd, v});
24            } else if (nd > dist1[v] && nd < dist2[v]) {
25                dist2[v] = nd;
26                q.push({nd, v});
27            }
28        }
29    }
30    cout << dist2[4];
31    return 0;
32}

单选题：程序输出是？（4 号点的次短路长度，要求严格大于最短路）

// 代码与 L1 完全相同，只是最后输出改为：
cout << dist1[3] << " " << dist2[3];

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 2});
09    int dist[2][5];                    // 第 0 层：没用免费；第 1 层：已用免费
10    memset(dist, 0x3f, sizeof dist);
11    dist[0][1] = 0;
12    // (距离, 已免费用掉的边数, 点)
13    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> q;
14    q.push({0, 0, 1});
15    while (!q.empty()) {
16        auto [d, f, u] = q.top(); q.pop();
17        if (d > dist[f][u]) continue;
18        for (auto [v, w] : g[u]) {
19            if (dist[f][v] > d + w) {         // 本条边正常付费
20                dist[f][v] = d + w;
21                q.push({d + w, f, v});
22            }
23            if (f == 0 && dist[1][v] > d) {   // 本条边免费（至多用一次）
24                dist[1][v] = d;
25                q.push({d, 1, v});
26            }
27        }
28    }
29    cout << dist[1][4];
30    return 0;
31}

单选题：程序输出是？（至多把一条边的费用改为 0，1 到 4 的最小费用）

01int nd = d + w;
02if (nd < dist1[v]) {
03    dist2[v] = dist1[v];
04    dist1[v] = nd;
05    q.push({nd, v});
06} else if (nd > dist1[v] && nd < dist2[v]) {
07    ______;              // 更新次短路
08    q.push({nd, v});
09}

单选题：横线处应填入？

// 图在 L1 基础上加一条边：1 -> 4，边权 4
g[1].push_back({4, 4});
// 其余代码与 L1 完全相同，最后输出 dist2[4]

单选题：程序输出是？（此时最短路为 4，次短路严格大于 4）

01// 代码与 L1 完全相同，最后输出 1~4 号点的次短路（INF 输出 INF）：
02for (int i = 1; i <= n; i++) {
03    if (dist2[i] == INF) cout << "INF"; else cout << dist2[i];
04    cout << " ";
05}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4, s = 1, t = 4;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 2});
09    int dist[5], pre[5], vis[5] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    dist[s] = 0;
12    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
13    q.push({0, s});
14    while (!q.empty()) {
15        auto [d, u] = q.top(); q.pop();
16        if (vis[u]) continue;
17        vis[u] = 1;
18        for (auto [v, w] : g[u])
19            if (dist[v] > d + w) {
20                dist[v] = d + w;
21                pre[v] = u;              // 记录前驱
22                q.push({dist[v], v});
23            }
24    }
25    vector<int> path;
26    for (int x = t; x != s; x = pre[x]) path.push_back(x);
27    path.push_back(s);
28    reverse(path.begin(), path.end());
29    for (int x : path) cout << x << " ";
30    return 0;
31}

单选题：程序输出是？（1 到 4 的最短路径）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5}); g[1].push_back({4, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 2});
09    int dist[5], cnt[5], vis[5] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    memset(cnt, 0, sizeof cnt);
12    dist[1] = 0; cnt[1] = 1;
13    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
14    q.push({0, 1});
15    while (!q.empty()) {
16        auto [d, u] = q.top(); q.pop();
17        if (vis[u]) continue;
18        vis[u] = 1;
19        for (auto [v, w] : g[u]) {
20            int nd = d + w;
21            if (nd < dist[v]) {
22                dist[v] = nd;
23                cnt[v] = cnt[u];         // 继承计数
24                q.push({nd, v});
25            } else if (nd == dist[v]) {
26                cnt[v] += cnt[u];        // 等长路径累加
27            }
28        }
29    }
30    cout << cnt[4];
31    return 0;
32}

单选题：程序输出是？（1 到 4 的最短路条数）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    bool r[5][5] = {};
06    r[1][2] = r[1][3] = r[2][3] = r[2][4] = r[3][4] = true;
07    for (int k = 1; k <= n; k++)
08        for (int i = 1; i <= n; i++)
09            for (int j = 1; j <= n; j++)
10                r[i][j] = r[i][j] || (r[i][k] && r[k][j]);
11    int cnt = 0;
12    for (int i = 1; i <= n; i++)
13        for (int j = 1; j <= n; j++)
14            if (i != j && r[i][j]) cnt++;
15    cout << cnt;
16    return 0;
17}

单选题：程序输出是？（i 能到达 j 的有序点对数，i ≠ j）

01int nd = d + w;
02if (nd < dist[v]) {
03    dist[v] = nd;
04    cnt[v] = cnt[u];
05    q.push({nd, v});
06} else if (nd == dist[v]) {
07    ______;              // 等长路径，计数累加
08}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4, s = 4;
05    vector<pair<int,int>> g[5];        // 反向建图：原边 u->v 变为 v->u
06    g[2].push_back({1, 2});
07    g[3].push_back({1, 5});
08    g[3].push_back({2, 1});
09    g[4].push_back({2, 6});
10    g[4].push_back({3, 2});
11    int dist[5], vis[5] = {0};
12    memset(dist, 0x3f, sizeof dist);
13    dist[s] = 0;
14    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
15    q.push({0, s});
16    while (!q.empty()) {
17        auto [d, u] = q.top(); q.pop();
18        if (vis[u]) continue;
19        vis[u] = 1;
20        for (auto [v, w] : g[u])
21            if (dist[v] > d + w) {
22                dist[v] = d + w;
23                q.push({dist[v], v});
24            }
25    }
26    cout << dist[1];
27    return 0;
28}

单选题：程序输出是？（等价于原图 1 到 4 的最短路）

// 图同 M2（含边 1->4 权 5），Dijkstra 同时维护 dist 与 cnt，
// 最后输出：
cout << dist[4] << " " << cnt[4];

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    vector<pair<int,int>> g[5];
06    g[1].push_back({2, 2}); g[1].push_back({3, 5});
07    g[2].push_back({3, 1}); g[2].push_back({4, 6});
08    g[3].push_back({4, 2});
09    int dist[5], vis[5] = {0};
10    memset(dist, 0x3f, sizeof dist);
11    dist[1] = 0;
12    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
13    q.push({0, 1});
14    while (!q.empty()) {
15        auto [d, u] = q.top(); q.pop();
16        if (vis[u]) continue;
17        vis[u] = 1;
18        for (auto [v, w] : g[u])
19            if (dist[v] > d + w) {
20                dist[v] = d + w;
21                q.push({dist[v], v});
22            }
23    }
24    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
25    return 0;
26}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    vector<pair<int,int>> g[4];
06    g[1].push_back({2, 2}); g[1].push_back({3, 3});
07    g[2].push_back({3, -1});
08    int dist[4], inq[4] = {0};
09    memset(dist, 0x3f, sizeof dist);
10    dist[1] = 0;
11    queue<int> q;
12    q.push(1); inq[1] = 1;
13    while (!q.empty()) {
14        int u = q.front(); q.pop();
15        inq[u] = 0;
16        for (auto [v, w] : g[u])
17            if (dist[v] > dist[u] + w) {
18                dist[v] = dist[u] + w;
19                if (!inq[v]) { q.push(v); inq[v] = 1; }
20            }
21    }
22    cout << dist[3];
23    return 0;
24}

单选题：程序输出是？（SPFA 处理含负权边的图）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    int d[5][5];
06    memset(d, 0x3f, sizeof d);
07    for (int i = 1; i <= n; i++) d[i][i] = 0;
08    d[1][2] = 2; d[1][3] = 5; d[2][3] = 1; d[2][4] = 6; d[3][4] = 2;
09    for (int k = 1; k <= n; k++)
10        for (int i = 1; i <= n; i++)
11            for (int j = 1; j <= n; j++)
12                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
13    cout << d[1][3] << " " << d[2][4];
14    return 0;
15}

单选题：程序输出是？

// 图同 L1，双重 dist 的 Dijkstra，最后输出：
cout << dist1[4] << " " << dist2[4];

单选题：程序输出是？

01for (int r = 1; r <= n - 1; r++)
02    for (auto [u, v, w] : e)
03        if (______)
04            dist[v] = dist[u] + w;

单选题：横线处应填入？

// SPFA + 入队次数判负环，图同 J4（含负权边但无负环）
// 最后输出：
cout << dist[1] << " " << dist[2] << " " << dist[3] << endl;
cout << "NO";

单选题：程序输出是？

01int n, m, dist[N], vis[N];
02vector<pair<int,int>> g[N];
03priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
04
05void dijkstra(int s) {
06    memset(dist, 0x3f, sizeof dist);
07    memset(vis, 0, sizeof vis);
08    dist[s] = 0;
09    q.push({0, s});
10    while (!q.empty()) {
11        auto [d, u] = ①;     // 取出当前距离最小的点
12        q.pop();
13        if (vis[u]) continue;
14        vis[u] = 1;
15        for (auto [v, w] : g[u])
16            if (dist[v] > d + w) {
17                dist[v] = d + w;
18                q.push({dist[v], v});
19            }
20    }
21}

单选题：①处应填？

01// edges 存所有边 (u, v, w)，n 为点数
02for (int i = 1; i <= ①; i++)          // 松弛 n-1 轮
03    for (auto [u, v, w] : edges)
04        if (dist[v] > dist[u] + w)
05            dist[v] = dist[u] + w;

单选题：①处应填？

01while (!q.empty()) {
02    int u = q.front(); q.pop();
03    ①;                            // 出队后清除入队标记
04    for (auto [v, w] : g[u])
05        if (dist[v] > dist[u] + w) {
06            dist[v] = dist[u] + w;
07            if (!inq[v]) {
08                q.push(v);
09                inq[v] = 1;
10            }
11        }
12}

单选题：①处应填？

01for (int k = 1; k <= n; k++)
02    for (int i = 1; i <= n; i++)
03        for (int j = 1; j <= n; j++)
04            d[i][j] = min(d[i][j], ②);   // 以 k 为中转点

单选题：②处应填？

01while (!q.empty()) {
02    auto [d, u] = q.top(); q.pop();
03    if (d > dist2[u]) continue;
04    for (auto [v, w] : g[u]) {
05        int nd = d + w;
06        if (nd < dist1[v]) {
07            dist2[v] = dist1[v];
08            dist1[v] = nd;
09            q.push({nd, v});
10        } else if (nd > dist1[v] && nd < dist2[v]) {
11            ①;                  // 更新次短路
12            q.push({nd, v});
13        }
14    }
15}

单选题：①处应填？

01// SPFA 中松弛成功时：
02cnt[v] = ①;                    // 记录 v 的松弛次数
03if (cnt[v] > n) { cout << "YES"; return 0; }

单选题：①处应填？

01for (auto [v, w] : g[u])
02    if (dist[v] > d + w) {
03        dist[v] = d + w;
04        ①;                   // 记录 v 的前驱
05        q.push({dist[v], v});
06    }
07// 输出路径：从终点 t 沿 pre 倒推回起点 s

单选题：①处应填？