P1119 灾后重建 分析

· · 个人记录

本题实际上和删边最短路差不多，都是考察对算法的理解。只不过这题是考察 Floyd，而我的删边最短路是考察 SPFA（其实我本来想把它做成一个 DP 题）。

已知每一个点的修建完成时间，实际上这就是每一个点的建立顺序。给定了一个时间，我们就知道存在哪些点，进一步知道我们可以用哪些边来组成这个最短路。

然后就很简单了。对于每次询问，我们找 t 时间内可以修建完成的点，然后用这些点来进行部分的 Floyd：即将最外层的 k 换成一个定点。然后就能得到 u 到 v 的最短路。

需要进行的检查是：因为进行 Floyd 时，所有能用的点已经是前面询问得到的，因此一定都是在当前时间前的（题目给定 t 单调不降）。于是我们只需要检查 u 与 v 现在修建完了没。

看来删边最短路也能评绿了（