灾后重建

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

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

OJ: luogu

题目 ID: P1119

难度:普及+/提高-

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

日期: 2026-07-17 03:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

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

思路

修复时间和询问时间都不下降。维护指针，把修复时间不晚于当前询问的村庄依次作为 Floyd 新中间点；每个中间点只加入一次。端点未修复或距离无穷时输出 -1。

Python 知识

  • 单调询问让一个 activated 指针代替每次重新计算。
  • 缓存矩阵行引用降低三重循环开销。
  • 10**18 作为整数无穷大，无浮点比较问题。

代码

python
import sys


input = sys.stdin.buffer.readline
n, edges = map(int, input().split())
ready = list(map(int, input().split()))
infinity = 10**18
distance = [[infinity] * n for _ in range(n)]
for node in range(n):
    distance[node][node] = 0
for _ in range(edges):
    u, v, weight = map(int, input().split())
    distance[u][v] = distance[v][u] = weight

activated = 0
answers = []
for _ in range(int(input())):
    start, end, time = map(int, input().split())
    while activated < n and ready[activated] <= time:
        middle = activated
        through = distance[middle]
        for x in range(n):
            row = distance[x]
            base = row[middle]
            for y in range(n):
                row[y] = min(row[y], base + through[y])
        activated += 1
    value = distance[start][end]
    answers.append(str(value if ready[start] <= time and ready[end] <= time and value < infinity else -1))
print("\n".join(answers))

原有 C++ 版本仍保留：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200 + 5;
const long long INF = (1LL << 60);

struct Query {
    int x, y, t, id;
};

int n, m;
int build_time[MAXN];
long long dist_arr[MAXN][MAXN];
Query queries[50000 + 5];
long long answer[50000 + 5];
int order_idx[MAXN];

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

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> build_time[i];
        order_idx[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist_arr[i][j] = 0;
            }
            else {
                dist_arr[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w < dist_arr[u][v]) {
            dist_arr[u][v] = dist_arr[v][u] = w;
        }
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].x >> queries[i].y >> queries[i].t;
        queries[i].id = i;
    }

    sort(order_idx, order_idx + n, [&](int a, int b) {
        return build_time[a] < build_time[b];
    });

    sort(queries + 1, queries + q + 1, [&](const Query &a, const Query &b) {
        return a.t < b.t;
    });

    int ptr = 0;

    // 按时间从小到大放开村庄。
    // 每放开一个新村庄 k，就做一轮 Floyd 的“加点转移”。
    for (int i = 1; i <= q; i++) {
        while (ptr < n && build_time[order_idx[ptr]] <= queries[i].t) {
            int k = order_idx[ptr];
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    if (dist_arr[x][k] + dist_arr[k][y] < dist_arr[x][y]) {
                        dist_arr[x][y] = dist_arr[x][k] + dist_arr[k][y];
                    }
                }
            }
            ptr++;
        }

        int x = queries[i].x;
        int y = queries[i].y;
        int t = queries[i].t;

        if (build_time[x] > t || build_time[y] > t || dist_arr[x][y] == INF) {
            answer[queries[i].id] = -1;
        }
        else {
            answer[queries[i].id] = dist_arr[x][y];
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

复杂度

总时间 O(n^3+Q)，空间 O(n^2)。

总结

Floyd 的中间点顺序可以与外部时间顺序同步，形成增量全源最短路。