这是一道考Floyd本质的题。
回忆一下Floyd的原理，三层循环，最外层循环枚举的是中转点，也就是用两点到中转点距离之和来更新最短路。然后来看下题目，重建时间是按照从小到大排序的，也就是说，当第i个村庄刚重建完成时，前i个村庄全部重建完成，而后面的都没有重建完成。那么在枚举中转点的时候就可以在线操作，如果当前询问时间比已经更新过的中转点now的时间大，则now++继续更新直到时间为当前询问时间，输出答案即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define B cout << "Break" << endl;
#define A(x) cout << #x << "=" << x << endl;
#define inf 1e9
using namespace std;
#define N 210
int t[N],dis[N][N],n,m;
void reset()
{
for(int i = ;i <= N;i++)
{
dis[i][i] = ;
for(int j = ;j <= N;j++)
{
if(i != j) dis[i][j] = inf;
}
}
return;
}
void floyd(int k)
{
for(int i = ;i < n;i++)
{
for(int j = ;j < n;j++)
{
dis[j][i] = dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);//Floyd板子
}
}
return;
}
int main()
{
reset();
scanf("%d %d",&n,&m);
for(int i = ;i < n;i++) scanf("%d",&t[i]);
for(int i = ;i < m;i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
dis[u][v] = dis[v][u] = w;
}
int cnt = ;
cin >> cnt;
int now = ;//用now记录当前枚举到的中转点
while(cnt--)
{
int a,b,tt;
scanf("%d %d %d",&a,&b,&tt);
while(t[now] <= tt && now < n)//如果now对应的时间比询问时间少则继续枚举中转点
{
floyd(now);
now++;
}
if(t[a] > tt || t[b] > tt || dis[a][b] == inf) printf("-1\n");//如果当前询问时间小于起点和终点的重建时间或者不连通则无解。
else printf("%d\n",dis[a][b]);
}
}