洛谷题单指南-最短路-P1119 灾后重建

原题链接：https://www.luogu.com.cn/problem/P1119

题意解读：n个节点的图，节点按时间依次可用，多个询问求某一时刻两点之间的最短路。

解题思路：

节点数只有200，很快能想到Floyd算法，但是如果只背过Floyd的模版，是不足以解决这道题，需要对Floyd算法的本质有深刻理解。

Floyd算法是基于动态规划的思想，先在一个小范围的节点中计算任意两点的最短路，再逐步扩大节点范围。

状态表示：可以设d[i][j][k]表示从i只经过1~k的节点走到j的最短路

状态转移：按照是否经过k分成两种情况，取最小值，d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

初始化：d[u][v][0] = w

根据以上的分析，这道题要求某个时刻两点的最短路，而某个时刻有多少点可以用，也是可以计算出来的：

设每个点恢复可用的时间用t[i]保存，为了便于floyd计算，节点我们都加1处理，范围由0 ~ n-1变成1 ~ n

这样给定一个时刻，有多少点可以用，通过int x = upper_bound(t + 1, t + n + 1, time) - t - 1即可计算出来最大的可用节点

直接根据状态表示的定义，即可得到这一时刻u->v的最短路是d[u][v][x]。

注意：

1、如果查询的时刻最大的可用节点x均比u或者v小，那么u或者v是不可达的，要输出-1。

2、如果d[u][v][x] = INF，表示u不能走到v，也要输出-1。

100分代码：

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

const int N = 205, Q = 50005, INF = 0x3f3f3f3f;
int d[N][N][N];
int t[N];
int n, m, q;

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof(d));
    for(int i = 1; i <= n; i++) cin >> t[i];
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++; v++;
        d[u][v][0] = d[v][u][0] = w;
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j][k] = min(d[i][k][k - 1] + d[k][j][k - 1], d[i][j][k - 1]);

    cin >> q;
    for(int i = 0; i < q; i++) 
    {
        int u, v, time;
        cin >> u >> v >> time;
        u++; v++;
        int x = upper_bound(t + 1, t + n + 1, time) - t - 1;
        if(u > x || v > x || d[u][v][x] == INF)
        {
            cout << -1 << endl;
        }
        else cout << d[u][v][x] << endl;
    }

    return 0;
}