JOISC2021 D2T1 Escape Route
好题.首先我们考虑一天之内能到达的情况.我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ,使得在 $T$ 之前的时刻出发,都可以在当天到达 $t$ (这里要注意有可能一天之内到不了,也就是可能 $T < 0$ ).
这个东西如何计算?首先有一种非常暴力的想法,我们每次加入一个当前连通块连出去的边,同时可能导致 $T$ 减小,然后重新跑一次最短路.考虑这样的复杂度,枚举点 $O(n)$ ,加边次数是 $O(n^2)$ ,每次跑最短路使用 dijkstra (这里显然 $O(n^2+m)$ 是优于 $O(m\log m)$ 的),复杂度就是 $O(n^5