洛谷 1119 灾后重建

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 #define rg register
 6 #define N 300
 7 using namespace std;
 8 int n,m,q,f[N][N],t[N],last,pointer;
 9 inline int read(){
10     int k=0,f=1; char c=getchar();
11     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
12     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
13     return k*f;
14 } 
15 int main(){
16     n=read(); m=read();
17     for(rg int i=1;i<=n;i++) t[i]=read();
18     for(rg int i=0;i<=n;i++)
19         for(rg int j=0;j<=n;j++)if(i!=j) f[i][j]=1e9; else f[i][j]=0;
20     for(rg int i=1,u,v;i<=m;i++) u=read()+1,v=read()+1,f[u][v]=f[v][u]=read();
21     q=read();
22     while(q--){
23         int x=read()+1,y=read()+1,time=read();
24         while(t[pointer]<=time&&pointer<=n) pointer++;
25         for(rg int k=last+1;k<pointer;k++)
26             for(rg int i=1;i<=n;i++)
27                 for(rg int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
28         printf("%d\n",(f[x][y]==1e9||t[x]>time||t[y]>time)?-1:f[x][y]);
29         last=pointer-1;
30     }
31     return 0;
32 }