本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-24 17:20:11

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

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

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

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

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