[Leaf] [P1119] 灾后重建

p1119-灾后重建---洛谷">P1119 灾后重建 - 洛谷

1. 题面梗概

中译中：有 $n$ 个村庄，有一些村庄被地震震坏了，需要 $t_i$ 时间修复。

现给定 $Q$ 次询问，问：$T$ 时刻，$x$ 村庄到 $y$ 村庄的最短路。

2. 逻辑推理

这一看就是个全源最短路问题。考虑 Floyd 算法，但是有时间限制，总不能对于每个村庄修好后都跑一次算法吧，那样复杂度为 $O(Q \cdot N^3)$，直接爆炸。

2.1 节点更新

我们发现，每次修好的村庄，确实会对所有村庄之间的路径产生影响。而 Floyd 算法也是如此，每次循环都寻找一个 $k$ 来更新 $i$ 点到 $j$ 点的距离。

平时背的模版可能是 $i \to j \to k$ ，但实际上应该是 $k \to i \to j$，我们只需要按照村庄修复时间，从早到晚进行枚举 $k$，即可应对动态查询。

2.2 结论

本题的关键在于理解 Floyd 算法松弛的原理。

3. 代码实现

▶

AcCode

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

const int maxn = 200 + 50;
const int maxm = 4e4 + 50;
const int inf = 1e9;

int ts[maxn];
int dist[maxn][maxn];
int n, m, q;

int main( )
{	
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j <= n; ++ j )
        {
            if( i == j ) dist[i][j] = 0;
            else dist[i][j] = inf; 
        }
    }

    for( int i = 1; i <= n; ++ i )
    {
        cin >> ts[i];
    }

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

    int k = 1;
    cin >> q;
    while( q -- )
    {
        int x, y, t;
        cin >> x >> y >> t;
        x ++, y ++;
        while( k <= n && ts[k] <= t )
        {
            for( int i = 1; i <= n; ++ i )
            {
                for( int j = 1; j <= n; ++ j )
                {
                    if( dist[i][k] != inf && dist[k][j] != inf )
                    {
                        dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
                    }
                }
            }
            k ++;
        }
        if( ts[x] > t || ts[y] > t || dist[x][y] == inf )
            cout << -1 << '\n';
        else
            cout << dist[x][y] << '\n'; 
    }
    return 0;
}

4. 复盘

• 复杂度分析：$O(N^3 + Q)$。

• 碎碎念：这道题是理解 Floyd 松弛操作的典例。它启发我们，Floyd 的外层循环其实是在做 动态规划的状态转移。

• 关联笔记：最短路体系