在洛谷中查看
解法1（我想的解法，不完全正确）:
很常见的套路：将询问按时间排序。时间复杂度：\(O(\;q\,(n\,logn+m)\;)\)，即 \(10^9\)，开 \(O2\) 才能过。
非常麻烦有没有，但我对拍的时候发现了一组数据很奇怪，待会给你们看看，我看看能不能 hack
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fi first
#define se second
const int N = 205, M = 2e4+5, Q = 5e4+5, element = 1e5+5;//注意数组大小，有点乱
int n,m,query_num,t[N],timeline[N],nxtdate[element],ans[Q];
struct edge{
int u,v,w;
};
vector<edge> g[element]; //每个时间都存一下
struct Query{
int u,v,t,id;
}q[Q];
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
return s*f;
}
bool cmp(Query a,Query b){
return a.t<b.t;
}
int road[N][N],dis[N];
priority_queue<P,vector<P>,greater<P> > Queue;
void dijkstra(int st){
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[st]=0;Queue.push(P(0,st));
while(!Queue.empty()){
P h=Queue.top();
Queue.pop();
int u=h.se;
if(dis[u]<h.fi)continue;
for(int i=1;i<=n;i++){
if(dis[i]>dis[u]+road[u][i]){
dis[i]=dis[u]+road[u][i];
Queue.push(P(dis[i],i));
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)t[i]=timeline[i]=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
u++,v++;
g[max(t[u],t[v])].push_back(edge{u,v,w});
}
sort(timeline+1,timeline+n+1);//将时间线从小到大排序
timeline[0]=-1;timeline[n+1]=element-1;//将timeline[0]的值设为 -1，并将timeline[n+1]的值设得比所有时间大，但也不能越界。让它有起点，有终点
for(int i=1;i<=n+1;i++)nxtdate[timeline[i-1]] = timeline[i];//像链表一样串起来
query_num=read();//变量名重了就很难受
for(int i=1;i<=query_num;i++)q[i]=Query{read()+1,read()+1,read(),i};
sort(q+1,q+query_num,cmp);
memset(road,0x3f,sizeof(road));//初始化
/*----------------------*/
//下面时间复杂度是 O( q(nlogn+m) ) 的，即最多 1e9 很悬
int now_time=-1;
for(int i=1;i<=query_num;i++){
if(q[i].u==q[i].v){ans[q[i].id]=0;continue;}//在同一个点时，不管建没建好，直接输出0
if(t[q[i].u]>q[i].t||t[q[i].v]>q[i].t){ans[q[i].id]=-1;continue;}
while(nxtdate[now_time]<=q[i].t){//总共只会有n次
now_time=nxtdate[now_time];
for(int build=0;build<g[now_time].size();build++){
int u=g[now_time][build].u,v=g[now_time][build].v,w=g[now_time][build].w;
road[u][v]=road[v][u]=min(road[u][v],w);
}
}
dijkstra(q[i].u);
ans[q[i].id]=(dis[q[i].v]==0x3f3f3f3f)?-1:dis[q[i].v];
}
for(int i=1;i<=query_num;i++)cout<<ans[i]<<endl;
return 0;
}