（自己想出来的一个最短路算法

众所周知，BFS 算法可以解决没有边权的最短路问题，例如下图有边权就无法解决：

但是我们可以拆边！

上图可以转化为：

这样就可以用 BFS 解决带边权的最短路问题了！

然后来计算一下复杂度

以https://www.luogu.com.cn/problem/P4779为例

因为边权是多少就会拆成多少条边，题目规定 $\sum w_i \leq 10^{9}$，所以会有 $10^{9}$ 条边。

BFS 的时间复杂度为 $O(n+m)$，带入得到该算法最坏时间复杂度为 $O(n+10^{9})$，众所周知常数可以忽略不计，所以我们就得到了 $O(n)$ 的单元最短路算法！常数只有 $10^{9}$！非常的优秀！$O(n)$ 的单元最短路比那个 dijkstra 好不知道多少倍！妙！！！