迪杰斯特拉复杂度O(Q*N log N)应该是可以过的吧

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int val,to,nxt;
}a[114514];
int n,m,t[114514],cnt,head[114514],Q,dist[114514];
bool vis[114514];
priority_queue<pair<int,int> >q;
void djs(int s,int f,int ti)
{
	memset(dist,0,sizeof dist);
	memset(vis,0,sizeof vis);
	for(int i=0;i<n;i++)
	{
		if(t[i]>ti)
			vis[i]=1;
		dist[i]=0x3f3f3f3f;
	}
	dist[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x])
			continue;
		vis[x]=1;
		for(int i=head[x];i;i=a[i].nxt)
		{
			int y=a[i].to;
			if(dist[y]>dist[x]+a[i].val&&!vis[y])
				dist[y]=dist[x]+a[i].val,q.push(make_pair(-dist[y],y));
		}
	}
}
void add(int x,int y,int z)
{
	a[++cnt].val=z;
	a[cnt].to=y;
	a[cnt].nxt=head[x];
	head[x]=cnt;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>t[i];
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
		add(y,x,w);
	}
	cin>>Q;
	while(Q--)
	{
		int s,f,ti;
		cin>>s>>f>>ti;
		djs(s,f,ti);
		if(t[s]>ti||t[f]>ti||dist[f]==0x3f3f3f3f)
		{
			cout<<-1<<endl;
			continue;
		}
		printf("%d\n",dist[f]);
	}
}