企业官网建设流程全解析

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,w，w ww不超过10000 1000010000，表示了有一条连接村庄i ii与村庄j jj的道路，长度为w ww，保证i ≠ j i\neq ji=j，且对于任意一对村庄只会存在一条道路。

接下来一行也就是M + 3 M+3M+3行包含一个正整数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

输入 #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 -1 5 4

说明/提示

• 对于30 % 30\%30%的数据，有N ≤ 50 N\le 50N≤50；
• 对于30 % 30\%30%的数据，有t i = 0 t_i=0ti​=0，其中有20 % 20\%20%的数据有t i = 0 t_i=0ti​=0且N > 50 N>50N>50；
• 对于50 % 50\%50%的数据，有Q ≤ 100 Q\le 100Q≤100；
• 对于100 % 100\%100%的数据，有1 ≤ N ≤ 200 1\le N\le 2001≤N≤200，0 ≤ 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。

解题思路

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=0x3f3f3f3f3f3f3f3fLL;constll M=1e6+10;constll mod=1e9+7;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 i=0;i<n;i++)f[i][i]=0;for(ll i=0;i<n;i++)scanf("%lld",&t[i]);for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&x,&y,&z);f[x][y]=f[y][x]=z;}scanf("%lld",&q);for(ll i=1;i<=q;i++){scanf("%lld%lld%lld",&fr[i],&to[i],&dy[i]);}for(ll l=1;l<=q;l++){for(ll k=0;k<n;k++){if(t[k]<=dy[l]&&!b[k]){b[k]=1;for(ll i=0;i<n;i++){for(ll j=0;j<n;j++){if(f[i][j]>f[i][k]+f[k][j]&&i!=j&&i!=k&&k!=j&&f[i][k]<INF&&f[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;}