跳到主要内容

AcWing 854. Floyd 求最短路

本节目标

按中转点阶段更新距离矩阵，回答多次任意两点最短路查询。

这是最短路中面向多次任意两点查询的母题。顶点数较小时，直接维护完整距离矩阵最稳定。

查看 AcWing 原题

题意与约束​

输入有向图和多组 (x, y) 查询，输出 x 到 y 的最短距离；不可达输出 impossible。重边应取最小值，对角线初始化为 0。

直接思路与瓶颈​

对每一组查询各跑一次单源最短路可以回答问题，但查询数多时会重复计算相同的路径信息；若用矩阵版 Dijkstra，总成本可达 O(q(n²+m))。本题顶点较少且要回答任意两点，直接预处理一张所有点对距离表更合适。

图模型与算法推导​

用矩阵 dist 表示当前已允许中转点范围下的全源距离：对角线为 0，直接边为最小边权，其余为无穷大。处理完编号 mid 后，dist[from][to] 表示只允许使用 1..mid 作为中转点时的最短距离。于是每轮固定一个 mid，再枚举起点和终点；仅当 from→mid、mid→to 都可达时，才比较经由 mid 的候选距离。

正确性依据​

对 mid 归纳。未开放任何中转点时，矩阵正好记录零条边或一条直接边的最短距离。假设开放 1..mid-1 后结论成立，任何只允许 1..mid 为中转点的最短路径要么不经过 mid，其长度已经在旧矩阵中；要么经过 mid，可拆成 from→mid 与 mid→to 两段，两段的内部中转点都只在 1..mid-1，由归纳假设其最短长度分别是旧矩阵对应项。取两类路径的较小者正是转移式，因此阶段不变量成立，最终矩阵即为所有点对最短路。

样例执行过程​

输入：

3 4 3
1 2 10
1 2 3
2 3 4
1 3 20
1 3
3 1
1 2

初始化（∞ 表示不可达，重边 1→2 取 3）：

     to: 1  2  3
from 1: 0  3 20
from 2: ∞  0  4
from 3: ∞  ∞  0
  1. 开放中转点 1：没有点能先到 1，矩阵不变。
  2. 开放中转点 2：检查 1→2→3，候选为 3+4=7，比原来的 20 小，将 dist[1][3] 改为 7；其他项不变。
  3. 开放中转点 3：3 没有到其他点的可达边，矩阵不变。查询依次得到 1→3=7、3→1=impossible、1→2=3。

代码实现​

C++17
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

const long long INF = numeric_limits<long long>::max() / 4;

void floyd(vector<vector<long long>>& dist) {
    const int n = static_cast<int>(dist.size()) - 1;
    for (int mid = 1; mid <= n; mid++) {
        for (int from = 1; from <= n; from++) {
            for (int to = 1; to <= n; to++) {
                if (dist[from][mid] < INF / 2 && dist[mid][to] < INF / 2) {
                    dist[from][to] = min(
                        dist[from][to], dist[from][mid] + dist[mid][to]
                    );
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, queries;
    cin >> n >> m >> queries;
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    for (int vertex = 1; vertex <= n; vertex++) dist[vertex][vertex] = 0;
    while (m--) {
        int from, to;
        long long weight;
        cin >> from >> to >> weight;
        dist[from][to] = min(dist[from][to], weight);
    }

    floyd(dist);

    while (queries--) {
        int from, to;
        cin >> from >> to;
        if (dist[from][to] > INF / 2) {
            cout << "impossible\n";
        } else {
            cout << dist[from][to] << '\n';
        }
    }
    return 0;
}

复杂度分析​

三重循环时间 O(n³)，距离矩阵空间 O(n²)；预处理后每个查询只需 O(1)。

边界与易错点​

  • mid 必须在最外层，否则阶段不变量不成立。
  • 先判断两段可达，再做加法。
  • 自身到自身为 0，重边保留较小值。
  • 判断不可达时使用足够大的无穷大阈值。

模式迁移​

当题目要求所有点对距离、顶点规模较小且查询很多时，优先考虑 Floyd；若只需单源且图更大，应回到 Dijkstra。