见题解： feilongz。
这里只放代码。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int Map[200][200]; bool vis[200]; int tme[200]; int main(){ int n=read(),m=read(); memset(Map,127/3,sizeof(Map)); for(int i=0;i<n;++i){ tme[i]=read(); Map[i][i]=0; } for(int i=1;i<=m;++i){ int from=read(),to=read(),dis=read(); if(Map[from][to]>dis) Map[from][to]=Map[to][from]=dis; } int Q=read(); for(int i=1;i<=Q;++i){ int from=read(),to=read(),t=read(); for(int j=0;j<n;++j){ if(vis[j]||tme[j]>tme[to]) continue; vis[j]=1; for(int k=0;k<n;++k) for(int l=0;l<n;++l) if(Map[k][l]>Map[k][j]+Map[j][l]) Map[k][l]=Map[k][j]+Map[j][l]; } if(tme[from]>t||tme[to]>t||Map[from][to]==Map[n][n]){ printf("-1 "); continue; } printf("%d ",Map[from][to]); } return 0; }