【题解】洛谷P1119 灾后重建

题目

洛谷P1119灾后重建

题解

由于询问数Q比较大,不可能每次询问都新建图,所以考虑离线(集中处理询问)。注意到村庄重建时间是不严格递增的,所以在时间t[i]之前,只有编号为0~i的村庄重建完。注意到村庄数n比较小,可以考虑floyd算法,这个算法可以求出任意两点间的最短路,同时,在动态规划过程中,floyd算法也解决了“若只经过编号为0~i的节点,求任意两点间的最短路径”这个子问题。所以,在执行floyd算法的同时,更新符合当前条件的询问的答案。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月21日 下午5:24

【小白解析】
此题主要思路演习floyd算法的模板,主要体现在第17行的“比较[现有的从i到j的路径长]与[从i到k再到j的路径长]并取最小值”的操作。
第13行至20行的两个循环看似复杂,实际从总体角度看很好理解。k所检索的是每一个村庄的情况,代表在此阶段中,1到k-1的村庄的情况已被考察,k为考察对象,而k+1到n的村庄情况均未更新;15至17行的i和j负责检索当前k所村庄已考察的情况下,所有线路的最短长度。
18行的i考察每一个问题:在仍有问题(i>=1),并且该问题所在的时间处于第k个村庄被修复之后(ti[k]<=a[i].t)时,该问题有考察意义。19行的a[i].x<=k&&a[i].y<=k保证问题涉及的村庄状态已更新完毕。
(此问题村庄修复时间单调递增,因此编号小于k的村庄在ti[k]时已近修复完成。此点感谢博主指出。)