题目背景

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

题目描述

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

#include<bits/stdc++.h>
using namespace std;
#define maxn 210
#define maxm 20010
#define maxw 1e9

int n,m,t[maxn],q,x,y,t2=0;
int d[maxn][maxn];

int main(){
	
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)  scanf("%d",&t[i]);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			d[i][j]=maxw;
		}
	}
	int u,v,w;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&u,&v,&w);
		d[u][v]=w;
		d[v][u]=w;
	}
		
	cin>>q;
	int k=0;
	while(q--){
		scanf("%d%d%d",&x,&y,&t2);
		if(t[x]>t2||t[y]>t2) {
			printf("-1\n");
			continue;
		}
		
		while(t[k]<=t2&&k<n){
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
			        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			k++;
		}
		if(d[x][y]>=maxw){
			printf("-1\n");
			continue;
		}
		printf("%d\n",d[x][y]);
	}
	return 0;
}