开 $O_2$: 100pts.

不开 $O_2$ :90pts.

真是个好氧,优化了大约10倍时间复杂度.

#include<bits/stdc++.h>
using namespace std;
#define Min(x,y) ((x)<(y) ? (x) : (y))
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m;
int t[210];
int e[210][210];
int nxt=1;
int main() {
	n=read(),m=read();
	memset(e,0x3f,sizeof e);
	for(int i=1;i<=n;i++) t[i]=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		u++,v++;
		e[u][v]=e[v][u]=w;
	}
	int q=read();
	while(q--){
		int x,y,t0;
		x=read(),y=read(),t0=read();
		x++,y++;
		for(int k=nxt;k<=n;k++){
			if(t[k]>t0){
				nxt=k;
				break;
			}
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					e[i][j]=Min(e[i][k]+e[k][j],e[i][j]);
		}
		if(t[x]>t0 || t[y]>t0 || e[x][y]==0x3f3f3f3f)
		    printf("-1\n");
		else printf("%d\n",e[x][y]);
	}
	return 0;
}