/*暴力暴力离线每次添边堆优化dij 70SPFA 80..... */#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#include<vector>#define maxn 210using namespace std;int n,m,Q,num,head[maxn],dis[maxn],t[maxn],f[maxn];queue<int>q;struct edge{    int v,pre,t;}e[maxn*maxn];struct node{    int u,v,r,t,ans;}p[maxn*maxn*2],P[maxn*maxn*2];int cmp1(const node &x,const node &y){    return x.t<y.t;}int cmp2(const node &x,const node &y){    return x.r<y.r;}void Add(int from,int to,int dis){    num++;e[num].v=to;    e[num].pre=head[from];    e[num].t=dis;    head[from]=num;}int SPFA(int u,int v,int now){    if(now<t[u]||now<t[v])return -1;    memset(dis,127/3,sizeof(dis));    memset(f,0,sizeof(f));    int inf=dis[0];f[u]=1;    dis[u]=0;q.push(u);    while(!q.empty()){        int k=q.front();q.pop();f[k]=0;        for(int i=head[k];i;i=e[i].pre){            int v=e[i].v;            if(dis[v]>dis[k]+e[i].t){                dis[v]=dis[k]+e[i].t;                if(f[v]==0){                    f[v]=1;q.push(v);                }            }        }    }    if(dis[v]==inf)return -1;    return dis[v];}int main(){    scanf("%d%d",&n,&m);    for(int i=0;i<n;i++)        scanf("%d",&t[i]);    int u,v,ti;    for(int i=1;i<=m;i++){        scanf("%d%d%d",&u,&v,&ti);        p[i].u=u;p[i].v=v;p[i].r=ti;        p[i].t=max(t[u],t[v]);    }    sort(p+1,p+1+m,cmp1);    scanf("%d",&Q);    for(int i=1;i<=Q;i++){        scanf("%d%d%d",&u,&v,&ti);        P[i].t=ti;P[i].u=u;        P[i].v=v;P[i].r=i;    }    sort(P+1,P+1+Q,cmp1);    int now=0,x=1;    for(int i=1;i<=Q;i++){        now=P[i].t;        while(p[x].t<=now&&x<=m){            Add(p[x].u,p[x].v,p[x].r);            Add(p[x].v,p[x].u,p[x].r);            x++;        }        P[i].ans=SPFA(P[i].u,P[i].v,now);    }    sort(P+1,P+1+Q,cmp2);    for(int i=1;i<=Q;i++)        printf("%d\n",P[i].ans);    return 0;}

/*加深了对floyed的理解实质是dp d[k][i][j] 表示i-j只经过1-k的节点作为中间点的最短路有两种情况 走或者不走kf[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])可以压缩空间压掉第一维嗯这个题各种提示用floyed啊首先t是小到大的 还有就是输入数据时不降的我还傻傻的离线sort做....结合题目每次询问i->j 保证中间经过的一定是修好了的城市只要满足 经过的在这之前都修好了那根据对floyed的理解 保证循环k<=t就好了 */#include<cstdio>#define maxn 210using namespace std;int n,m,k,Q,t[maxn],f[maxn][maxn],inf;int min(int x,int y){    return x<y?x:y;}int init(){    int x=0;char s=getchar();    while(s<‘0‘||s>‘9‘)s=getchar();    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x;}int Floyed(int u,int v,int ti){    if(t[u]>ti||t[v]>ti)return -1;    for(;k<n&&t[k]<=ti;k++)        for(int i=0;i<n;i++)            for(int j=0;j<n;j++)                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);    if(f[u][v]==inf)return -1;    else return f[u][v];}int main(){    n=init();m=init();    for(int i=0;i<n;i++)        t[i]=init();    int u,v,ti;    inf=0x3f3f3f3f;    for(int i=0;i<=n;i++)        for(int j=0;j<=n;j++)            f[i][j]=inf;    for(int i=0;i<n;i++)        f[i][i]=0;    for(int i=1;i<=m;i++){        u=init();v=init();ti=init();        f[u][v]=f[v][u]=ti;    }    Q=init();    while(Q--){        u=init();v=init();ti=init();        printf("%d\n",Floyed(u,v,ti));    }    return 0;}