https://www.luogu.com.cn/problem/P1119

题目背景

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

题目描述

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

输入格式

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

第二行包含 N 个非负整数 t0≤t1≤…≤t**N−1。

接下来M行，每行 3个非负整数i,j,w，ww为不超过 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

1
2
3
4
5
6
7
8
9
10
11
12
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
2
3
4
-1
-1
5
4

利用 floyd 每次加入一个点的特点…

有多次查询，维护一个 last time , 如果本次查询 t <= last 则 T[ v ] <= last 的无需再计算。总的下来只需要跑一边 Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int INF=0x3f3f3f3f;
const int MAX=200+5;
int n,m,T[MAX],t,g[MAX][MAX],x,y,w,q,d[MAX][MAX],last; 
void floyd(int v,int t){
	if(T[v]>last && T[v]<=t)
		fi(i,0,n)
		fi(j,0,n)
			if(d[i][v]+d[v][j]<d[i][j])
				d[i][j]=d[i][v]+d[v][j];
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);
	fi(i,0,n)
		sf(T[i]);
	fi(i,0,n)
		fi(j,i+1,n){
			g[i][j]=INF;g[j][i]=INF;
		}
	while(m--){
		sf(x);sf(y);sf(w);
		g[x][y]=w;
		g[y][x]=w;
	}
	fi(i,0,n)
		fi(j,0,n){
			d[i][j]=g[i][j];
		}
	sf(q);
	last=-1;
	while(q--){
		sf(x);sf(y);sf(t);
		fi(i,0,n)
			floyd(i,t);
		last = max(last,t);
		if(d[x][y]==INF || T[x]>t ||T[y]>t)pfc("-1");
		else pf(d[x][y]);
		pfc("\n");
	}
	return 0;
}