本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-12-15 22:34:35

$\color{green}\text{AC算法：}$ floyd

题目描述

有 $N$ 个村庄，$M$条公路，编号为 $0 \rightarrow N-1$。每个村庄都有一个修复完成时间 $ti$，为 $0$ 则不需要修复。
有 $q$ 个询问，每次询问在第 $t$ 天，$x \rightarrow y$ 的最短路。保证每次询问 $t$ 是不下降的。

题目分析：

观察一下数据范围，$n \le 200$ ，这明显是在暗示使用 floyd这种 $O(n^{3})$ 暴力来求最短路。同时如此小的数据范围可以用邻接矩阵。
可以用一个结构体 $czok$ 存储每个村庄的修复时间。用另一个结构体 $node$ 存储每组询问。可以将 $node$ 数组从按照 $t$ 的大小从小到大排序，为什么这么做之后会解释。

解题过程

读入完成后，就是刚才说的将 $node$ 数组从小到大排序。然后处理每一组询问。
对于每一组询问，可以依次遍历 $n$ 个点求最短路。但是这样复杂度为 $O(QN^{3})$，恭喜你TLE了。
想一想优化，这时候就可以利用每组询问的 $t$ 不下降的性质了。可以定义一个变量 $pos = 0$ ,遍历每组询问时从pos开始遍历，如果当前点 $pos$已经被修复，那么从 $pos$ 跑一遍floyd，然后 pos++ ，知道 $pos$ 没有被修复。可以发现，因为每组询问的 $t$ （第 $t$ 天）是不下降的，所以在之前询问中已经修复的点在当前询问中也一定已经修复，不用重新从已经跑过floyd的点中重新再跑一遍，这样每个点最多运行一次floyd，时间复杂度降为 $O(q + n^{3})$，可以AC。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f = -1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n,m;
int dis[205][205];\/\/距离，邻接矩阵
bool vis[205];\/\/判断是否已经有了答案
int q;
struct Node{
    int u, t, time;
    int bh;
    int ans;
}node[50005];
struct Czok{
    int bh;\/\/它的编号
    int time;\/\/修复时间
}czok[205];
bool cmp(Node a,Node b){
    return a.time < b.time;
}
bool cmpbh(Node a,Node b){
    return a.bh < b.bh;
}
inline void floyd(int mid){
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= n;j++){
            dis[i][j]=min(dis[i][j],dis[i][mid]+dis[mid][j]);
        }
    }
}
int main(){
    memset(dis, 0x3f, sizeof(dis));
    n = read();
    m = read();
    for (int i = 1; i <= n;i++){
        dis[i][i] = 0;
    }
    for (int i = 1; i <= n; i++){
        czok[i].time = read();
        czok[i].bh = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, t, v;
        u = read();
        t = read();
        v = read();
        u++;\/\/因为题目中起点是由0开始的，这里使用下标1，所以下标++
        t++;
        dis[u][t] = min(dis[u][t],v);\/\/重边保留最小
        dis[t][u] = min(dis[t][u], v);
    }
    q = read();
    for (int i = 1; i <= q;i++){
        int u, t, time;
        u = read();
        t = read();
        time = read();
        u++;\/\/原理同上
        t++;
        node[i].bh=i;
        node[i].u = u;
        node[i].t = t;
        node[i].time = time;
    }
    sort(node + 1, node + q + 1, cmp);
    int pos = 1;\/\/遍历所有村庄，遇到修复的就跑一边floyd
    for (int i = 1; i <= q;i++)
    {
        while(czok[pos].time<=node[i].time&&pos<=n){
            \/\/如果已经修复完成，并且没有越界，跑一边floyd
            int bh=czok[pos].bh;
            floyd(bh);
            vis[bh] = 1;
            pos++;
        }
        if(!vis[node[i].u]||!vis[node[i].t]||dis[node[i].u][node[i].t]>100000000)
            node[i].ans = -1;
        else
            node[i].ans = dis[node[i].u][node[i].t];
    }
    sort(node + 1, node + q + 1, cmpbh);
    for (int i = 1; i <= q;i++){
        cout << node[i].ans << endl;
    }
    return 0;
}