最短路算法

单源最短路无负边->朴素Dijkstra->O(n^2)稠密图用

单源最短路无负边->堆优化Dijkstra->O(mlogn)稀疏图用
vector写邻接表用Dijkstra_heap的时候会很难受
因为vector< PII > g[N] fi = 终点 se = 花费
queue< PII, vector< PII >, greater< PII > > q fi = dist[i] se = i 起点
这里st[i]的作用是标记 i 已经被加入到了最短路集合中
根据Dijkstra的性质 绝对不会有新的dist[i] 小于现有的dist[i]
当然是没有负数边的情况下

单源最短路有负边->Bellman-Ford->O(n^3)一般不用

单源最短路有负边->SPFA->O(m)极限被卡O(nm)
SPFA是对Bellman-Ford的宽搜优化
因为dist[b] = min(dist[b], dist[a] + w);
当dist[a]变小的时候dist[b]才会有更新
用一个queue来存能变小的dist[a]
用一个st[N]来标记dist[a]是否已经被放入队列（毕竟最多只能进队一次）

AcWing 1129. 热浪 （邻接矩阵，朴素Dijkstra）（SPFA）（堆优化Dijkstra）