spfa求最短路
$spfa$算法概述
$spfa$是对$bellman$-$ford$的优化,$bellman$-$ford$算法中的松弛操作不是每一次都会进行的,不进行的部分就是冗余操作,我们就是针对这一部分进行优化
只有边的起点的$dist$变化,才会连锁导致边的终点的$dist$变化。我们每次将变化的点都入队,然后遍历它的出边
因为需要遍历出边,所以这里图的存储采用邻接表
这里我们为了避免重复操作,已经在队列中的元素不再入队,因为它一定在下次出队的时候会更新完所有的。不在队列中的元素变化后直接入队。
判断条件问题
因为本题更新只会更新到能由起点到达的点,不可达的点不会更新,所以最后判断未到达的点距离是否等于$0x3f3f3f3f$是可以的
代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx; // 邻接表
int dist[N];
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数组
dist[1] = 0;
queue<int> q;
q.push(1); // 起点入队
st[1] = true; // 该点已经在队列中
while (q.size())
{
int t = q.front();
q.pop(); // 取队头
st[t] = false; // 该点不在队列中
for (int i = h[t]; i != -1; i = ne[i]) // 遍历所有出边
{
int j = e[i];
if (dist[j] > dist[t] + w[i]) // 更新
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果该点不在队列中,就将它入队
{
q.push(j); // 入队
st[j] = true; // 该点已在队列中
}
}
}
}
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f) puts("impossible"); // 判断是否可达
else printf("%d\n", t);
return 0;
}