#P1119. 灾后重建

灾后重建

题目背景

B 地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的公路均无法通车。换句话说,只有连接着两个重建完成的村庄的公路才能通车,只能到达重建完成的村庄。

题目描述

给出 B 地区的村庄数 NN,村庄编号从 00N1N-1,和所有 MM 条公路的长度,公路是双向的。并给出第 ii 个村庄重建完成的时间 tit_i,你可以认为是同时开始重建并在第 tit_i 天重建完成,并且在当天即可通车。若 tit_i00 则说明地震未对此地区造成损坏,一开始就可以通车。之后有 QQ 个询问 (x,y,t)(x,y,t),对于每个询问你要回答在第 tt 天,从村庄 xx 到村庄 yy 的最短路径长度为多少。如果无法找到从 xx 村庄到 yy 村庄的路径,经过若干个已重建完成的村庄,或者村庄 xx 或村庄 yy 在第 tt 天仍未重建完成,则需要输出 1-1

输入格式

第一行包含两个正整数 N,MN,M,表示了村庄的数目与公路的数量。

第二行包含 NN 个非负整数 t0,t1,,tN1t_0,t_1,\cdots,t_{N-1},表示了每个村庄重建完成的时间,数据保证了 t0t1tN1t_0 \le t_1 \le \cdots \le t_{N-1}

接下来 MM 行,每行 33 个非负整数 i,j,wi,j,www 为不超过 1000010000 的正整数,表示了有一条连接村庄 ii 与村庄 jj 的道路,长度为 ww,保证 iji\neq j,且对于任意一对村庄只会存在一条道路。

接下来一行也就是 M+3M+3 行包含一个正整数 QQ,表示 QQ 个询问。

接下来 QQ 行,每行 33 个非负整数 x,y,tx,y,t,询问在第 tt 天,从村庄 xx 到村庄 yy 的最短路径长度为多少,数据保证了 tt 是不下降的。

输出格式

QQ 行,对每一个询问 (x,y,t)(x,y,t) 输出对应的答案,即在第 tt 天,从村庄 xx 到村庄 yy 的最短路径长度为多少。如果在第 tt 天无法找到从 xx 村庄到 yy 村庄的路径,经过若干个已重建完成的村庄,或者村庄 xx 或村庄 yy 在第 tt 天仍未修复完成,则输出 1-1

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4
-1
-1
5
4

提示

  • 对于 30%30\% 的数据,有 N50N\le 50
  • 对于 30%30\% 的数据,有 ti=0t_i=0,其中有 20%20\% 的数据有 ti=0t_i=0N>50N>50
  • 对于 50%50\% 的数据,有 Q100Q\le 100
  • 对于 100%100\% 的数据,有 1N2001\le N\le 2000MN×(N1)20\le M\le \dfrac{N\times(N-1)}{2}1Q500001\le Q\le 50000,所有输入数据涉及整数均不超过 10510^5