ABC375 笔记

Garbage_fish · 2024-10-16 18:36:53 · 个人记录

没打，全是场后。

G

按完申请就不接受新题解了（

一次最短路 + 一次 Tarjan。

先跑一次以 1 为起点的最短路，将所有能构成最短路的边丢进一张新图里，如果某条边是这张新图的割边，就意味着删掉这条边之后，必须要绕不是最短路的路径走才有可能到达 n，答案变大，输出 \texttt{Yes}。

怎么判断某条边是否会构成最短路呢？假设当前 Dijkstra 处理到 u，如果有一条边 (u,v,w) 可以使得 dis_v+w=dis_u，那这就是一条最短路上的边。

因为现在处理 u 说明 dis_u 已经是最优，边权全为正数所以 dis_v<dis_u，也是最优值。

F

断边不好操作可以考虑离线下来时光倒流，建边，跑 Floyd，每连一条边就看一下每一组 dis(u,v) 是原本优还是经过连的这条边更优。O(n^3+\sum_{opt=1}n^2)。

自我感觉这题比 G 难，G 太板了。