这道题我用dij做的,代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2e2+1,M=1e5+1;
struct jgt{
	int x,y;
	bool operator < (const jgt & a) const{
		return y>a.y;
	}
};
int n,m,q,cnt,x,y,w;
int t[N],flag[M],cc[N],l[N],r[N];
int cj[N],ok[N],dis[N][N][N];
vector<jgt> lj[N];
priority_queue<jgt> d;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&t[i]);
		if(!flag[t[i]]){
			flag[t[i]]=1,r[cc[0]]=i-1;
			cc[++cc[0]]=t[i],l[cc[0]]=i;
		}
	}
	r[cc[0]]=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		lj[x+1].push_back({y+1,w});
		lj[y+1].push_back({x+1,w});
	}
	for(int i=1;i<=cc[0];i++){
		for(int j=l[i];j<=r[i];j++){
			cj[j]=1;
		}
		for(int j=1;j<=r[i];j++){
			for(int k=1;k<=r[i];k++){
				dis[i][j][k]=INT_MAX;
			}
		}
		for(int j=1;j<=r[i];j++){
			dis[i][j][j]=0;
			d.push({j,0});
			while(!d.empty()){
				jgt zx=d.top();
				d.pop();
				if(dis[i][j][zx.x]!=zx.y){
					continue;
				} 
				for(int l=0;l<lj[zx.x].size();l++){
					if(dis[i][j][lj[zx.x][l].x]>dis[i][j][zx.x]+lj[zx.x][l].y){
						dis[i][j][lj[zx.x][l].x]=dis[i][j][zx.x]+lj[zx.x][l].y;
						d.push({lj[zx.x][l].x,dis[i][j][lj[zx.x][l].x]});
					}
				}
			}
		}
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&x,&y,&w);
		x++,y++;
		if(t[x]>w||t[y]>w){
			printf("-1\n");
			continue;
		}
		for(int i=cc[0];i>=1;i--){
			if(w>=cc[i]){
				if(dis[i][x][y]!=INT_MAX){
					printf("%d\n",dis[i][x][y]);
				}
				else{
					printf("-1\n");
				}
				break;
			}
		}
	}
	return 0;
}

之前一直会T，好像就是因为在第 $49$ 行 if(dis[i][j][lj[zx.x][l].x]>dis[i][j][zx.x]+lj[zx.x][l].y){ 这个if语句里面加了个 lj[zx.x][l].x<=r[i] 的条件，意思是当前遍历到的这个村庄还没有重建，也就不可能到达，这样按理能让堆中少一些无用的点，但是加上后却变慢了很多。