题解：CF1998D Determine Winning Islands in Race

传送门

思路简介

我们考虑什么时候 Bessie 不能赢下比赛：当且仅当 Elsie 能够从 Bessie 起点之前的点，通过额外的路径比 Bessie 先走到某个点。充分性显然，必要性也不难理解：假如 Elsie 无法做到这一点，她永远不可能走到 Bessie 之前，因此她不可能赢得比赛。我们设这个点为，Bessie此时的起点为，Elsie 在当前状态下走到的最短时间为，那么可以列出式子，移项得到，那么我们只需要维护的最大值，而与无关了。我们考虑如何得到。我们考虑从到枚举，并在此同时加入起点在之前的每一条边，那么每一条新加入的边我们可以得到一个新的。对于每一条边，是一定的，即为走到起点的最短时间加上。难道我们还要每次加入一条边还跑一次最短路？其实不然。令这条边的起点为，假如我们求出了在之前的每个点的最小到达时间，考虑计算时间的式子，是一定的，我们只需要求出的最小值就可以了，我们可以用线段树做到这一点。同时考虑到，只有新加的边可能会对时间造成影响，我们只需要在加入一条边的同时更新即可。对于一组数据，时间复杂度为。

代码

提交记录