灾后重建

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int INF=0x3f;
 6 int i,j,n,m,dis[205][205],t[40005],q,k,a,b,c;
 7 void Floyd(){
 8     int i,j;
 9     for(;k<=n;k++)
10         if(t[k]<=c)
11             for(i=1;i<=n;i++)
12                 for(j=1;j<=n;j++)
13                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
14         else break;
15 }
16 int main(){
17     //freopen("1119.in","r",stdin);
18     //freopen("1119.out","w",stdout);
19     scanf("%d%d",&n,&m);
20     memset(dis,0x3f,sizeof(dis)); 
21     memset(t,0x3f,sizeof(t)); 
22     for(i=1;i<=n;i++)
23         scanf("%d",&t[i]);
24     for(i=1;i<=n;i++)
25         dis[i][i]=0;
26     for(i=1;i<=m;i++){
27         scanf("%d%d%d",&a,&b,&c);
28         a++;
29         b++;
30         dis[a][b]=dis[b][a]=c;
31     }
32     scanf("%d",&q);
33     k=1;
34     while(q--){
35         scanf("%d%d%d",&a,&b,&c);
36         a++;
37         b++;
38         Floyd();
39         if(dis[a][b]==0x3f3f3f3f||t[a]>c||t[b]>c) 
40             printf("-1\n");
41         else printf("%d\n",dis[a][b]);
42      }
43     return 0;
44 }