西蒙·弗洛伊德曾经说过一句很有哲理的话,叫做:

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

题意描述:

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

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

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

现在,给出B地区的村庄数N,村庄编号从0N1,和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%的数据,有N50

对于另外30%的数据,t[i]=0

对于50%的数据,有Q100

对于100%的数据,有N200Q50000,所有输入数据均为int型整数且均不超过100000


分析

一道Floyd好题

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

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

  1. n的取值范围极小,只有200.(疯狂暗示

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

  3. 本题可以在线求解

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

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

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

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

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

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

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

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

是不是很简单啊(逃)~


附件(AC标程,防作弊已开启)

cpp
#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