图论、最短路、Floyd、环
枚举环上三个相邻节点 $i,j,k$，环的长度即为 $(i,k),(k,j)$ 的长度之和加上从 $i$ 到达 $j$ 且不经过 $k$ 的最短路长度。由于 Floyd 在最外层枚举中转点 $k$ 之前求得的所有不以 $k$ 为端点的最短路都不经过节点 $k$，在更新最短路之前枚举 $i,j$ 并使用当前的中转点 $k$ 拼环取最小值即可得到答案。
最后修改：2024 年 05 月 26 日
© 允许规范转载