搜索与图论 ---- spfa 求最短路 及 输出路径

spfa 算法是对 bellmen-ford 算法的一个优化，bellmen-ford 算法在更新最短路的时候需要遍历所有的边，而 spfa 只是用刚被更新过的点去更新与它相连的点的边，因为只有更被更新过的点才有机会去更新下一个点

dist [ j ] = dist [ i ] + w ( i , j ) ,若 dist [ j ] 要被更新则 dist [ i ] 一定更被更新，才能使得 dist [ j ] 被更新

int spfa()
{
    memset(dist,0x3f,sizeof dist);queue<int> q;q.push(1);st[1]=true;dist[1]=0;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];pre[j]=t;if(!st[j]){
    q.push(j);st[j]=true;}}}}if(dist[n]==0x3f3f3f3f) return -1;return dist[n];
}

spfa 输出路径

// 初始化 for(int i=1;i<=n;i++) pre[i]=i;
void print(int st,int ed)
{
    if(st==ed){
    cout<<st<<" ";return ;}print(st,pre[ed]);cout<<ed<<endl;
}

题目链接

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

2

spfa : 存在负环

代码样例

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>#define x first
#define y secondusing namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;}
int lowbit(int x) {
    return x & -x;}int n, m;
int h[N], e[N], ne[N], w[N], idx;
queue<int> q;
int dist[N];
bool st[N];void add(int a, int b, int c)
{
    e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx ++ ;
}bool spfa()
{
    memset(dist, 0x3f, sizeof dist);dist[1] = 0;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]){
    st[j] = true;q.push(j);}}}}if(dist[n] == 0x3f3f3f3f) return false;return true;}int main()
{
    cin >> n >> m;memset(h, -1, sizeof h);for(int i = 0; i < m; i ++ ){
    int a, b, c;cin >> a >> b >> c;add(a, b, c);}spfa();if(spfa()) cout << dist[n] << endl;else cout << "impossible" << endl;return 0;
}