luogu P1119 灾后重建

佚名 6年前 (2019-04-12) 随笔 637人围观抢沙发百度已收录

接近弗洛伊德板子，唯一的不同点是对每组 i j k 特判一下在给定时间内三点间的道路是否修建完成。

而且由于给出的t都单调不减，那么显然在询问较大的t时，比其更小的t时的状态已经维护过一遍，因此可以记录维护时间的最大值。每次询问时用while（sign<t）来限制即可保证只考虑该t下已修好的道路。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

复杂度为O（n^3）

// luogu-judger-enable-o2
#include<cstdio> #include<algorithm> #include<cstring>
#define maxn 210
#define inf 35481215
using namespace std; int mp[maxn][maxn]; int que[maxn],n,m,q,k=0; void floyd(int x,int y,int t) { while(que[k]<=t) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); k++; } if(mp[x][y]==0x3f3f3f3f||que[x]>t||que[y]>t) printf("-1\n"); else printf("%d\n",mp[x][y]); } int main() { memset(mp,0x3f,sizeof(mp)); memset(que,0x3f,sizeof(que)); scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&que[i]),mp[i][i]=0; for(int i=1,x,y,w;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); mp[x][y]=mp[y][x]=w; } scanf("%d",&q); for(int i=1,x,y,t;i<=q;i++) { scanf("%d%d%d",&x,&y,&t); floyd(x,y,t); } return 0; }