灾后重建 - 洛谷
/** @Description: To iterate is human, to recurse divine.* @Autor: Recursion* @Date: 2022-03-11 10:05:27* @LastEditTime: 2022-03-11 20:24:50*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int T[205];
int G[500][500];
void updata(int k)
{for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(G[i][j]>G[i][k]+G[k][j])G[i][j]=G[j][i]=G[i][k]+G[k][j];return;
}int main()
{cin>>n>>m;for(int i=0;i<n;i++)cin>>T[i];// for(int i=0;i<n;i++)//不能用memset，会炸，只有-1和0能用for(int i=0;i<n;i++){for(int j=0;j<n;j++)G[i][j]=1e9;}for(int i=0;i<n;i++)G[i][i]=0;// for(int i=0;i<n;i++){// for(int j=0;j<n;j++)// cout<<G[i][j]<<" ";// cout<<endl;// }int x,y,w;for(int i=1;i<=m;i++){cin>>x>>y>>w;G[x][y]=G[y][x]=w;}int Q,now=0,t;cin>>Q;for(int i=1;i<=Q;i++){cin>>x>>y>>w;while(T[now]<=w&&now<n){updata(now);now++;}if(T[x]>w||T[y]>w) cout<<-1<<endl;else{if(G[x][y]==1e9) cout<<-1<<endl;else cout<<G[x][y]<<endl;}}}