131D
CF131D Subway 题解
题目传送门 前置知识 强连通分量 | 最短路 解法 考虑用 Tarjan 进行缩点,然后跑最短路。 缩点:本题的缩点有些特殊,基于有向图缩点修改而得,因为是无向图,所以在 Tarjan 过程中要额外记录一下从何处转移过来,防止在同一处一直循环。 基环树上找环还有其他方法,这里仅讲解使用 Tarjan ......
CF131D的题解
注意到 $n$ 实在是小到不行,我们可以直接采用比较暴力的做法。 ~~(嗯,可能算比较暴力吧~~ 很简单,找环,然后把环里的所有点全部压进 `dijkstra` 的优先队列就行了。 找环最坏 $n$ 遍跑满的 `dfs`,最短路是 $O(n\log n)$ 的,最坏时间复杂度为 $O(n^2)$,稳 ......