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 42 43 44 45 46 47 48 49 50 51 52
| #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm>
using namespace std; typedef long long ll; #define R register #define I inline template<class T>void read(T &x) { register int c = getchar(), f = 1; x = 0; while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();} while(isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f; } const int maxm=205*204/2, maxn=210; int n,m,cur,time[maxn],dis[maxn][maxn];
int main(){ memset(dis,0x3f,sizeof(dis)); memset(time,0x3f,sizeof(time)); scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d",&time[i]); dis[i][i]=0; } for(int i=1;i<=m;i++) { int u,v,c; scanf("%d%d%d",&u,&v,&c); dis[u][v]=dis[v][u]=c; } int Q; scanf("%d",&Q); while(Q--) { int x,y,t; scanf("%d%d%d",&x,&y,&t); while(time[cur]<=t) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) dis[i][j]=min(dis[i][j],dis[i][cur]+dis[cur][j]); cur++; } if(dis[x][y]==0x3f3f3f3f || time[x]>t || time[y]>t) printf("-1\n"); else printf("%d\n",dis[x][y]); } return 0; }
|