给定一个 \(n\) 个点 \(m\) 条边的有边权无向图，其中边权 \(w_i\in \{0,1,\dots,k-1\}\)，求点 \(1\) 到各个点的最短路。
期望复杂度：\(O((n+m)k)\)
0k最短路
在经典的 Dijkstra 算法中，我们使用一个优先队列来维护松弛队列，这样的时间复杂度为 \(O((n+m)\log k)\)。现在我们考虑为每种边权开一个松弛队列（一共 \(k\) 个松弛队列）。对于某个特定的边权 \(w\)，由于松弛后的距离都是 \(\text{dis}[u]+w\) 的形式，所以不需要用优先队列，直接保留原来取出顶点的顺序就好。每次循环时枚举所有 \(k\) 个队列找最小的队列即可。
例题：
标签：松弛,队列,边权,复杂度,常数,短路 From： https://www.cnblogs.com/szdytom/p/how-did-we-get-here-5.html