spfa算法(队列优化的Bellman-Ford算法)
注:一般情况下效率高于Bellman-Ford算法,但不能包含负环(99.9%没限制),也可以解决 正权图的题,
比如能过掉 AcWing 850. Dijkstra求最短路 II ,而且效率更快(除去极特殊用例卡最坏情况)。
时间复杂度:平均情况下$O(m)$,最坏情况下$O(nm)$,$n$表示点数,$m$表示边数
思路:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
int n, m; // n个点m条边
int h[N], e[N], w[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点是否在队列中
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 初始化所有点的距离
queue<int> q; // 定义队列存储所有待更新的点
q.push(1); // 1号点入队列
st[1] = true; // 标记该点,确定该点已放在队列里
while(q.size())
{
auto t = q.front(); q.pop(); //取出队头
st[t] = false; // 该点不在队列中
//更新所有出边
for(int i = h[t]; i != -1; i = ne[i]) // 扫描所有出边
{
int j = e[i]; // 找到出边,j存储编号
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i]; //更新出边j的最短距离
if(!st[j]) // 如果队列中已存在j,则不需将j重复插入
{
q.push(j); // 若j不在队列中,把j加入队列里
st[j] = true; //标记该点在队列中
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1; // 1 ~ n不连通,返回-1
return dist[n]; // 返回第n个点到源点的最短距离
}
int main()
{
cin >> n >> m;
// 构建邻接表
memset(h, -1, sizeof h); // 初始化所有表头
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if(t == -1) puts("impossible");
else cout << t << endl;
return 0;
}