TL;DR：这是一个求解无向图（非负实数边权）上单源最短路问题，期望复杂度为 $O(n \sqrt{\log n \log \log n})$ 的非确定性做法。（以下讨论均默认 $n,m$ 同阶...

1. 无向图包含每个点的最小（边）简单环有基于分治的 $O(n^3 \log n)$ 做法，此处略去。有以下重要结论：对于每个点 $p$ 建以 $p$ 为根的最短路树，我们只需考虑两端点 $\t...