【洛谷精选】灾后重建-题解

西蒙・弗洛伊德曾经说过一句很有哲理的话，叫做：

$$f[i][j]=min(f[i][j],f[i][k]+f[k][j]);$$

题意描述：

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。

但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。

换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

现在，给出$B$ 地区的村庄数$N$，村庄编号从$0$ 到$N-1$，和$M$ 条公路的长度。

公路是双向的。并给出第$i$ 个村庄重建完成的时间$t[i]$

若$t[i]$ 为$0$ 则说明地震未对此地区造成损坏，一开始就可以通车。

之后有$Q$ 个询问$(x,y,t)$

对于每个询问你要回答在第$t$ 天，从村庄$x$ 到村庄$y$ 的最短路径长度为多少。

如果无法找到从$x$ 村庄到$y$ 村庄的路径，或者村庄$x$ 或村庄$y$ 在第$t$ 天仍未重建完成 ，则输出$-1$。

---

输入格式：

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

第二行包含$N$ 个非负整数$t$ 表示了每个村庄重建完成的时间.

接下来$M$ 行，每行$3$ 个非负整数$i,j,w$, 表示了有一条连接村庄$i$ 与村庄$j$ 的道路

接下来一行包含一个正整数$Q$，表示$Q$ 个询问。

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

---

输出格式：

共$Q$ 行，对每一个询问$(x,y,t)$ 输出对应的答案。

如果在第$t$ 天无法找到从$x$ 村庄到$y$ 村庄的路径，或者村庄$x$ 或村庄$y$ 在第$t$ 天仍未修复完成，则输出$-1$。

---

Input & Output ‘s examples

Input ‘s eg

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

Output ‘s eg

-1
-1
5
4

---

数据范围和约定

对于$30\mathrm{\%}$ 的数据，有$N\le 50$；

对于另外$30\mathrm{\%}$ 的数据，$\mathrm{有}t[i]=0$

对于$50\mathrm{\%}$ 的数据，有$Q\le 100$

对于$100$$\mathrm{\%}$ 的数据，有$N\le 200$，$Q\le 50000$，所有输入数据均为$int$ 型整数且均不超过$100000$。

---

分析

一道$Floyd$ 好题

彻底刷新了我对$Floyd$ 的看法。

首先，我们认真读一遍题目，不难发现以下几点

1. $n$ 的取值范围极小，只有 200.（疯狂暗示

2. $t$ 不下降（即$t$ 是按时间顺序从小到大给出的）

3. 本题可以在线求解

4. 村庄标号从 0 开始（坑了我一次提交机会）

现在我们一起看一下$Floyd$ 算法的主要思想。

$Floyd$ 算法基于 DP，说白了，就是用最外层循环不停的枚举每两个点之间的中间点来进行松弛操作。

而在本题中，每一个村庄是否可以作为中间点取决于它是否重建完成。也就是说，在村庄重建完成之前，它不可以作为中间点进行枚举

所以我们只需要将最外层用来枚举中间点的循环加一个特判，判断该点能否被用来中转即可。

但要注意，如果起点或终点没有完成重建，需要输出 - 1

因此，我们还需要进行一次特判，用于判断起点与重点是否重建完成。

一个$Floyd$ + 两个特判 = 一道蓝题

是不是很简单啊（逃）~

---

附件（AC 标程，防作弊已开启）

#include<iostream>
#define N 201 

using namespace std;

int n , m;
int a[N];
int l , r , w;
int f[N][N];	//由于本题数据范围较小，作者采用邻接矩阵存图 
int q;
int x , y , t;

void floyd(int k){		//Floyd主体函数 
	for(int i = 0; i <= n - 1; i ++){
		for(int j = 0; j <= n - 1; j ++){
			f[i][j] = min(f[i][j] , f[i][k] + f[k][j]); 
		}
	}
}

int main(){
	cin >> n >> m;
	for(int i = 0; i <= n - 1; i ++){
		cin >> a[i];
	}
	for(int i = 0; i <= n - 1; i ++){
		for(int j = 0; j <= n - 1; j ++){
			f[i][j] = 1e9;		//初始化邻接矩阵 
		}
	}
	for(int i = 0; i <= n - 1; i ++){
		f[i][i] = 0;
	}
	for(int i = 0; i <= m - 1; i ++){
		cin >> l >> r >> w;
		f[l][r] = w;		//由于是双向道路，所以需要建两次边 
		f[r][l] = w;
	}
	cin >> q;
	int now = 0;	//now代表今天是第几天，用于枚举天数 
	for(int i = 0; i <= q - 1; i ++){
		cin >> x >> y >> t;
		if(a[x] > t || a[y] > t){	//特判，如果起点或终点就没有重建，直接跳过循环 
			cout << "-1" <<endl;
			continue;
		}
		while(a[now] <= t && now < n){
			floyd(now);
			now ++;
		}
		if(f[x][y] == 1e9){		//如果没有联通路，输出-1 
			cout << "-1" <<endl;
		}
		else{ 
			cout << f[x][y] << endl;
		}
	}
	return 0;
}
//Written By Payphone-X 

---

THE END