题目背景

$B$地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出$B$地区的村庄数$N$，村庄编号从$0$到$N-1$，和所有$M$条公路的长度，公路是双向的。并给出第$i$个村庄重建完成的时间$t_i$，你可以认为是同时开始重建并在第$t_i$天重建完成，并且在当天即可通车。若$t_i$为$0$则说明地震未对此地区造成损坏，一开始就可以通车。之后有$Q$个询问$(x, y, t)$，对于每个询问你要回答在第$t$天，从村庄$x$到村庄$y$的最短路径长度为多少。如果无法找到从$x$村庄到$y$村庄的路径，经过若干个已重建完成的村庄，或者村庄$x$或村庄$y$在第$t$天仍未重建完成，则需要返回$-1$。

输入输出格式

输入格式：

第一行包含两个正整数$N,M$，表示了村庄的数目与公路的数量。

第二行包含$N$个非负整数$t_0, t_1,…, t_{N-1}$，表示了每个村庄重建完成的时间，数据保证了$t_0 ≤ t_1 ≤ … ≤ t_{N-1}$。

接下来$M$行，每行$3$个非负整数$i, j, w$，$w$为不超过$10000$的正整数，表示了有一条连接村庄$i$与村庄$j$的道路，长度为$w$，保证$i≠j$，且对于任意一对村庄只会存在一条道路。

接下来一行也就是$M+3$行包含一个正整数$Q$，表示$Q$个询问。

接下来$Q$行，每行$3$个非负整数$x, y, t$，询问在第$t$天，从村庄$x$到村庄$y$的最短路径长度为多少，数据保证了$t$是不下降的。

输出格式：

共$Q$行，对每一个询问$(x, y, t)$输出对应的答案，即在第$t$天，从村庄$x$到村庄$y$的最短路径长度为多少。如果在第$t$天无法找到从$x$村庄到$y$村庄的路径，经过若干个已重建完成的村庄，或者村庄$x$或村庄$y$在第$t$天仍未修复完成，则输出$-1$。

输入输出样例

输入样例#1：

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

输出样例#1：

-1
-1
5
4

说明

对于$30\%$的数据，有$N≤50$；

对于$30\%$的数据，有$t_i= 0$，其中有20\%20%的数据有$t_i = 0$且$N>50$；

对于$50\%$的数据，有$Q≤100$；

对于$100\%$的数据，有$N≤200$，$M≤N \times (N-1)/2$，$Q≤50000$，所有输入数据涉及整数均不超过$100000$。

说明

本题基本上是Floyd的模版题，适合初学Floyd的OIer练习。

本题的重点在于并非在每一个时刻，每一个节点都可以到达，所以应枚举目前所有可以到达的节点k，并以k为中转点进行更新。

同时，因为出题人已经给数据排好了顺序，发现未建成时直接中断即可。

闲话少说，主要看代码注释。

#代码

#include<cstdio> 
#include<algorithm>
using namespace std;

const int MAXN = 200 + 5;
const int INF = 1e9;

int edge[MAXN][MAXN], times[MAXN];
int n, m, q;

/*
init()函数：
Floyd初始化
*/
void init() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            edge[i][j] = (i == j ? 0 : INF);//节点到自身的距离为0
        }
    }
}

/*
addEdge()函数：
在邻接矩阵中添加一条（双向）边
*/
void addEdge(int i, int j, int v) {
    edge[i][j] = edge[j][i] = v;//双向边处理
}

/*
input()函数：
输入数据
*/
void input() {
    scanf("%d%d", &n, &m);
    init(); //读入n, m后进行初始化
    for(int i = 0; i < n; i++) {
        scanf("%d", &times[i]);
    }
    for(int i = 0; i < m; i++) {
        int x, y, v;

        scanf("%d%d%d", &x, &y, &v);
        addEdge(x, y, v);
    }
}

/*
update()函数：
以k为中转点更新最短路
*/
void update(int k) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
        }
    }
}

void work() {
    int cur = 0;

    scanf("%d", &q);
    for(int i = 0; i < q; i++) {
        int x, y, t;

        scanf("%d%d%d", &x, &y, &t);

        //这里是重点
        while(times[cur] <= t && cur < n) {
            update(cur);//若当前可以经过村庄cur，以cur为中转点更新最短路径
                        cur++;
        }
        if(times[x] > t || times[y] > t || edge[x][y] == INF) {
            printf("-1\n");//村庄x尚未建成,村庄x尚未建成或村庄x与村庄y在t时并不连通
        } else {
            printf("%d\n", edge[x][y]);
        }
    }
}

int main() { //简洁的main()函数
    input();
    work();

    return 0;
}

版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 许可协议。转载请注明出处！
本文链接：https://keepthethink.github.io/archives/1827780785/