灾后重建

GitHub跳转原题关系图返回列表

按时间增量加入 Floyd 中间点，在线回答当前已重建村庄间最短路。

OJ: luogu

题目 ID: P1119

难度:普及+/提高-

标签:Floyd离线询问增量算法python

创建: 2026-07-17 03:00

更新: 2026-10-20 16:07

后置题目

roj 3183「Sightseeing trip」观光之旅B 的「先探测、再并入」直接把 A 教的「逐个加入新中间点做一轮 Floyd 增量松弛」当作第二阶段，并依赖其阶段语义（并入 k 之前 dist 只经过更早的中间点）来定义拆环所需的受限最短路，在此之上再叠加最小环建模、候选环探测与中转点表回溯

题意

村庄按时间修复，询问某天只经过已修复村庄的最短路。

思路

直接做法：每个询问重算一次。

对每个询问 $t$ ，只保留重建时间不晚于 $t$ 的村庄与它们之间的公路，跑一次 Floyd，读出 d[x][y]。这个做法完全符合题意，但代价是 $Q \cdot N^3$ ：

Q \cdot N^3 = 5\times 10^4 \times 8\times 10^6 = 4\times 10^{11}

必超时。卡点在于：相邻两次询问之间图几乎没变——村庄只会被修复，不会被摧毁，所以“已开放的点集”只增不减，全额重算把 $99.9\%$ 相同的计算又做了一遍。

转折：看清 Floyd 的 `middle` 到底是什么

Floyd 的三层循环通常会写成一个纯粹的循环变量，但它有明确语义：

d^{(k)}[i][j] = \text{只允许经过前 } k \text{ 个点作为中转时，} i \text{ 到 } j \text{ 的最短路}

也就是说，middle 不是在“迭代次数”，而在控制允许使用的中转点集合。跑完第 $k$ 轮后，矩阵里就是“只用前 $k$ 批点中转”的最短路。

把这两件事对照起来，就会发现它们长得一模一样：

时间轴	Floyd 的 `middle`
时间 $t$ ，已修复的村庄集合	已跑完的 `k` 轮，已允许的中转点集合
只增不减	只增不减
下个时刻新增一批村庄	下轮 `k` 新增一个中转点

于是 middle 可以跟着时间走：把村庄按重建时间排好，询问按时间排好，用一个指针记录“当前已开放到哪个村庄”；每开放一个新村庄就让它当一次 middle，做一轮加点转移。

几个容易搞混的点

middle 必须“从小到大”吗？ 不一定。Floyd 的 k 顺序其实是任意的，只要每个点恰好当一次 k，最终结果都是正确的全源最短路（中间状态不同，不动点相同）。

那为什么这里没选编号顺序？因为我们要在扫描过程中直接回答询问，所以中间状态必须对应一个真实时刻。选时间序，第 $k$ 轮后的矩阵恰好就是第 $t_k$ 天的答案；选别的顺序，中间状态并无现实含义，就问不了。

复用旧矩阵为什么不会出错？ 这是必须说清的一点，不是“看起来应该没问题”。新增中转点只会让最短路变短或不变（多一条可选绕路），所以旧矩阵里每一格都是新矩阵的上界，不会成为错的答案。随后那轮 middle 转移会把可以变短的格子全部修正好。

这个“单调收紧⇒复用安全”的论证一旦失效，整道题的做法就崩，见后文边界。

总代价为什么降到 $N^3$ ？ 因为所有询问共享同一条 middle 序列。N 个点在整个程序里各只当一次 k，所以 k 循环总计只跑 $N$ 轮，而不是每个询问跑 $N$ 轮。这是均摊：每个询问只花 $O(1)$ 查表。

边界

端点未修复： $t_x > t$ 或 $t_y > t$ 时直接输出 $-1$ ，哪怕矩阵里已经有值（那个值可能经过了尚未修复的点）。
不连通：d[x][y] 仍为 INF 时输出 $-1$ 。
为什么依赖 $t$ 不降：单向推进的指针要求询问时间非降。若询问乱序，需要先离线排序再回答（本题题面已保证非降，直接用即可）。
若村庄能反复摧毁重建：已开放集合不再单调，旧矩阵可能变得过于乐观，这套增量做法立即失效，必须换成分治或线段树分治等结构。

Python 知识

单调询问让一个 activated 指针代替每次重新计算。
缓存矩阵行引用降低三重循环开销。
10**18 作为整数无穷大，无浮点比较问题。
多层条件用布尔与短路求值压成一行：ready[start] <= time and ready[end] <= time and value < infinity，写入前就能把 $-1$ 的三种情形全筛掉。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-17 01:40
# update_at: 2026-10-20 16:20
#
# main.py：灾后重建。村庄按时间修复，询问某天只经过已修复村庄的最短路。
# 朴素做法是对每个询问重建图再跑一次 Floyd，代价 Q*N^3 必超时。
# 关键：Floyd 的中间点 middle 不是在“迭代次数”，而是在控制“允许使用的中转点集合”，
# 已经跑完 k 轮就代表允许经过前 k 批点中转。而村庄只会修复不会摧毁，
# 所以已开放集合只增不减 —— 这两件事结构相同，就把 middle 交给时间轴：
#   村庄按修复时间排好、询问按时间排好，用指针 activated 记录开放到哪，
#   每开放一个新村庄就让它当一次 middle，做一轮加点转移。
# N 个点全程各只当一次中间点，总代价 O(N^3 + Q)，而不是 O(Q*N^3)。
# 复用旧矩阵的前提是单调收紧：新增中转点只会让最短路变短或不变，
# 所以旧值恒为新值的上界，不会成为错误答案。

import sys

INF = 10**18  # 整数哨兵，比任何合法路径都大，无浮点比较问题


def solve() -> None:
    # 一次性读入全部整数再顺序消费：比逐行 input() 少大量 IO 与解析开销
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    ready = [next(data) for _ in range(n)]  # 题面保证 ready 非降序

    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        # 公路是双向的；题面保证任意两点之间只有一条路，不必取 min
        dist[u][v] = dist[v][u] = w

    activated = 0  # 已经放开到哪个村庄，值就是“下一次要用的 middle”
    answers: list[str] = []

    Q = next(data)
    for _ in range(Q):
        start, end, day = next(data), next(data), next(data)

        # 把重建时间不晚于今天、但还没当中间点用过的村庄依次放开。
        # 每放开一个就做一轮 Floyd 加点转移：允许经过它的路径可能更短。
        while activated < n and ready[activated] <= day:
            middle = activated
            through = dist[middle]  # dist[middle][*]，缓存行引用
            for x in range(n):
                row = dist[x]
                base = row[middle]  # dist[x][middle]
                if base == INF:
                    continue  # x 到 middle 不可达，这一轮对 x 没有改善
                for y in range(n):
                    candidate = base + through[y]
                    if candidate < row[y]:
                        row[y] = candidate
            activated += 1

        # 三种输出 -1 的情形合成一个判断：端点未修复 / 距离仍无穷
        value = dist[start][end]
        reachable = ready[start] <= day and ready[end] <= day and value < INF
        answers.append(str(value if reachable else -1))

    print("\n".join(answers))


if __name__ == "__main__":
    solve()

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-10-20 15:45
 */
// 灾后重建：村庄按时间修复，询问某天只经过已修复村庄的最短路。
// 朴素做法是对每个询问重建图再跑一次 Floyd，代价 Q*N^3 必超时。
// 关键：Floyd 的中间点 k 不是在"迭代次数"，而是在控制"允许使用的中转点集合"，
// 跑完 k 轮就代表允许经过前 k 批点中转。而村庄只会修复不会摧毁，
// 所以已开放集合只增不减 —— 这两件事结构相同，就把 k 交给时间轴：
//   题面保证 t_i 非降、询问的 t 也非降，所以可以边读询问边往前推进指针，
//   每放开一个新村庄就让它当一次 k，做一轮 Floyd 加点转移。
// N 个点全程各只当一次中间点，总代价 O(N^3 + Q)，而不是 O(Q*N^3)。
// 复用旧矩阵的前提是单调收紧：新增中转点只会让最短路变短或不变，
// 所以旧值恒为新值的上界，不会成为错误答案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;              // 村庄数上界 N <= 200
const long long INF = (1LL << 60);

int n, m;
int ready_day[MAXN];               // ready_day[i]：i 号村庄第几天修复完成
long long dist_node[MAXN][MAXN];   // dist_node[i][j]：只用已开放村庄中转的最短路

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> ready_day[i];  // 题面保证非降序

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist_node[i][j] = (i == j) ? 0 : INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        // 公路双向；题面保证任意两点间只有一条路，直接赋值即可
        dist_node[u][v] = w;
        dist_node[v][u] = w;
    }

    int activated = 0;  // 已经放开到哪个村庄，它同时也是"下一次要用的 k"
    int query_cnt;
    cin >> query_cnt;

    for (int i = 0; i < query_cnt; i++) {
        int start, end, day;
        cin >> start >> end >> day;

        // 把修复时间不晚于今天、但还没当过中间点的村庄依次放开。
        // 每放开一个就做一轮 Floyd 加点转移：允许经过它的路径可能更短。
        while (activated < n && ready_day[activated] <= day) {
            int middle = activated;
            for (int x = 0; x < n; x++) {
                if (dist_node[x][middle] == INF) continue;  // x 到 middle 不可达，这一轮对 x 无改善
                long long base = dist_node[x][middle];
                for (int y = 0; y < n; y++) {
                    long long candidate = base + dist_node[middle][y];
                    if (candidate < dist_node[x][y]) {
                        dist_node[x][y] = candidate;
                    }
                }
            }
            activated++;
        }

        // 三种输出 -1 的情形：起点未修复、终点未修复、仍然不可达
        if (ready_day[start] > day || ready_day[end] > day || dist_node[start][end] == INF) {
            cout << -1 << '\n';
        } else {
            cout << dist_node[start][end] << '\n';
        }
    }

    return 0;
}

复杂度

Floyd 的 middle 一共只被当作中转点 $N$ 次，所以总时间 $O(N^3 + Q)$ ，空间 $O(N^2)$ 。

对比未优化的 $O(Q \cdot N^3)$ ，差距是 $Q$ 倍（本题 $5\times 10^4$ 倍）。实测 $N=200$ 完全图、 $Q=50000$ 的最坏数据，Python 版约 1.7 秒。

总结

Floyd 的 middle 层不是在“迭代次数”，而是在控制“允许使用的中转点集合”。己知这个集合只增不减，就把 middle 交给时间轴：N 个点全程各当一次中间点，总代价从 $Q \cdot N^3$ 降到 $N^3$ 。

复用旧矩阵的前提是单调收紧：新增中转点只会让距离变短或不变。一旦集合不再单调（比如村庄可以反复摧毁），这个前提就不成立。

P1119 灾后重建

题目背景

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出 B 地区的村庄数 $N$ ，村庄编号从 $0$ 到 $N-1$ ，和所有 $M$ 条公路的长度，公路是双向的。并给出第 $i$ 个村庄重建完成的时间 $t_i$ ，你可以认为是同时开始重建并在第 $t_i$ 天重建完成，并且在当天即可通车。若 $t_i$ 为 $0$ 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 $Q$ 个询问 $(x,y,t)$ ，对于每个询问你要回答在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未重建完成，则需要输出 $-1$ 。

输入格式

第一行包含两个正整数 $N,M$ ，表示了村庄的数目与公路的数量。

第二行包含 $N$ 个非负整数 $t_0,t_1,\cdots,t_{N-1}$ ，表示了每个村庄重建完成的时间，数据保证了 $t_0 \le t_1 \le \cdots \le t_{N-1}$ 。

接下来 $M$ 行，每行 $3$ 个非负整数 $i,j,w$ ， $w$ 不超过 $10000$ ，表示了有一条连接村庄 $i$ 与村庄 $j$ 的道路，长度为 $w$ ，保证 $i\neq j$ ，且对于任意一对村庄只会存在一条道路。

接下来一行也就是 $M+3$ 行包含一个正整数 $Q$ ，表示 $Q$ 个询问。

接下来 $Q$ 行，每行 $3$ 个非负整数 $x,y,t$ ，询问在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少，数据保证了 $t$ 是不下降的。

输出格式

共 $Q$ 行，对每一个询问 $(x,y,t)$ 输出对应的答案，即在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果在第 $t$ 天无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未修复完成，则输出 $-1$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

对于 $30\%$ 的数据，有 $N\le 50$ ；
对于 $30\%$ 的数据，有 $t_i=0$ ，其中有 $20\%$ 的数据有 $t_i=0$ 且 $N>50$ ；
对于 $50\%$ 的数据，有 $Q\le 100$ ；
对于 $100\%$ 的数据，有 $1\le N\le 200$ ， $0\le M\le \dfrac{N\times(N-1)}{2}$ ， $1\le Q\le 50000$ ，所有输入数据涉及整数均不超过 $10^5$ 。

灾后重建

目录

题意

思路

转折：看清 Floyd 的 middle 到底是什么

几个容易搞混的点

边界

Python 知识

代码

复杂度

总结

转折：看清 Floyd 的 `middle` 到底是什么