P1119 灾后重建网页链接添加链接描述题目背景B 地区在地震过后所有村庄都遭受了一定的损毁而这场地震却没对公路造成什么影响。但是在村庄重建好之前所有与未重建完成的村庄相连的公路均无法通车。换句话说只有连接着两个重建完成的村庄的公路才能通车只能到达重建完成的村庄。题目描述给出 B 地区的村庄数N NN村庄编号从0 00到N − 1 N-1N−1和所有M MM条公路的长度公路是双向的。并给出第i ii个村庄重建完成的时间t i t_iti​你可以认为是同时开始重建并在第t i t_iti​天重建完成并且在当天即可通车。若t i t_iti​为0 00则说明地震未对此地区造成损坏一开始就可以通车。之后有Q QQ个询问( x , y , t ) (x,y,t)(x,y,t)对于每个询问你要回答在第t tt天从村庄x xx到村庄y yy的最短路径长度为多少。如果无法找到从x xx村庄到y yy村庄的路径经过若干个已重建完成的村庄或者村庄x xx或村庄y yy在第t tt天仍未重建完成则需要输出− 1 -1−1。输入格式第一行包含两个正整数N , M N,MN,M表示了村庄的数目与公路的数量。第二行包含N NN个非负整数t 0 , t 1 , ⋯ , t N − 1 t_0,t_1,\cdots,t_{N-1}t0​,t1​,⋯,tN−1​表示了每个村庄重建完成的时间数据保证了t 0 ≤ t 1 ≤ ⋯ ≤ t N − 1 t_0 \le t_1 \le \cdots \le t_{N-1}t0​≤t1​≤⋯≤tN−1​。接下来M MM行每行3 33个非负整数i , j , w i,j,wi,j,ww ww不超过10000 1000010000表示了有一条连接村庄i ii与村庄j jj的道路长度为w ww保证i ≠ j i\neq jij且对于任意一对村庄只会存在一条道路。接下来一行也就是M 3 M3M3行包含一个正整数Q QQ表示Q QQ个询问。接下来Q QQ行每行3 33个非负整数x , y , t x,y,tx,y,t询问在第t tt天从村庄x xx到村庄y yy的最短路径长度为多少数据保证了t tt是不下降的。输出格式共Q QQ行对每一个询问( x , y , t ) (x,y,t)(x,y,t)输出对应的答案即在第t tt天从村庄x xx到村庄y yy的最短路径长度为多少。如果在第t tt天无法找到从x xx村庄到y yy村庄的路径经过若干个已重建完成的村庄或者村庄x xx或村庄y yy在第t tt天仍未修复完成则输出− 1 -1−1。输入输出样例 #1输入 #14 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 -1 5 4说明/提示对于30 % 30\%30%的数据有N ≤ 50 N\le 50N≤50对于30 % 30\%30%的数据有t i 0 t_i0ti​0其中有20 % 20\%20%的数据有t i 0 t_i0ti​0且N 50 N50N50对于50 % 50\%50%的数据有Q ≤ 100 Q\le 100Q≤100对于100 % 100\%100%的数据有1 ≤ N ≤ 200 1\le N\le 2001≤N≤2000 ≤ M ≤ N × ( N − 1 ) 2 0\le M\le \dfrac{N\times(N-1)}{2}0≤M≤2N×(N−1)​1 ≤ Q ≤ 50000 1\le Q\le 500001≤Q≤50000所有输入数据涉及整数均不超过10 5 10^5105。解题思路代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF0x3f3f3f3f3f3f3f3fLL;constll M1e610;constll mod1e97;boolb[201];ll n,m,x,y,z,q;ll t[201];ll f[201][201];ll fr[50001],to[50001],dy[50001];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(f,0x3f,sizeof(f));scanf(%lld%lld,n,m);for(ll i0;in;i)f[i][i]0;for(ll i0;in;i)scanf(%lld,t[i]);for(ll i1;im;i){scanf(%lld%lld%lld,x,y,z);f[x][y]f[y][x]z;}scanf(%lld,q);for(ll i1;iq;i){scanf(%lld%lld%lld,fr[i],to[i],dy[i]);}for(ll l1;lq;l){for(ll k0;kn;k){if(t[k]dy[l]!b[k]){b[k]1;for(ll i0;in;i){for(ll j0;jn;j){if(f[i][j]f[i][k]f[k][j]i!ji!kk!jf[i][k]INFf[k][j]INF)f[i][j]f[i][k]f[k][j];}}}}if(t[fr[l]]dy[l]t[to[l]]dy[l]f[fr[l]][to[l]]!INF)printf(%lld\n,f[fr[l]][to[l]]);elseprintf(-1\n);}return0;}