P1119 灾后重建

题目链接P1119 灾后重建
先读题意，就是求在 \(t\) 时间时当前 \(a\) 到 \(b\) 的最短路，并且当前 \(a\) 和 \(b\) 村都必须重建完毕。即然一两点间距离。再看一眼数据范围，可以知道需要用到 Floyd 算法。

比较暴力的，可能会用 \(n\) 次 Floyd 把每次时间的两点间距算出，但这样是 \(O(n^4)\) 时间太高。
根据题意，有村庄修复有时间的限制，实际上，时间的限制不就是可通过村子的限制吗，再回想一下 Floyd 的方程，不就是在前可通过前 \(k\) 个点中，两点间最短距离吗？只要考虑到这点，这题就简单了。

比较好玩的，题目中点是 \(0\) 到 \(n - 1\) 的，我们可以把所有点 \(+1\) 变成 \(1\) 到 \(n\) 的便于操作。

题目很仁慈，村庄重建完成的时间和询问的时间都是不降的，这就不用我们去排序了。
因为是不降的，对于每次询问有个时间 \(t\)，我们需要知道在 \(t\) 时有对少个村庄已经修复，这是什么？二分查找。在重建时间中二分，取最大的重建时间小于等于 \(t\) 的点，把这个询问加进，这个点的询问序列中。因为询问时间不降，你加进去的序列也就是不降的，且符合询问的顺序，也就不需要我们再去映射了。注意，二分的时候要存在时间为 \(0\) 的点。

到这题目就基本结束了，看看代码吧。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 210, M = 50010;

int n, m;
int g[N][N];
int t[M];

struct Node
{
    int a, b, t;
}res[M];

vector<Node> q[N]; // 对于每个点i的询问

int find(int x) // 二分
{
    int l = 0, r = n;
    
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (x >= t[mid]) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    cin >> n >> m;
    
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> t[i];
        g[i][i] = 0;
    }
    
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a ++ , b ++ ;  // 平移，点的坐标
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    cin >> m;
    
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a ++ , b ++ ;
        res[i] = {a, b, c}; // 存储的原询问，其实可以和下面一步写在一起，省空间
    }
    
    for (int i = 1; i <= m; i ++ ) // 分配询问
    {
        int x = find(res[i].t);
        q[x].push_back(res[i]);
    }
    
    for (int k = 0; k <= n; k ++ ) // 注意从0开始，防止有t = 0的询问，而重建时间里没有0
    {
        for (int i = 1; i <= n; i ++ ) // 基本的 Floyd 
            for (int j = 1; j <= n; j ++ )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        for (auto r : q[k]) // 解决当前点的询问，即在r询问的时间时，前k个村庄已经修复
        {
            int w = g[r.a][r.b];
            if (t[r.a] > r.t || t[r.b] > r.t) cout << -1 << endl;
            else if (w <= 0x3f3f3f3f / 2) cout << w << endl;
            else cout << -1 << endl;
        }
    }
    return 0;
}