单源最短路奇技淫巧之SPFA算法

引入

之前我讲了另一个求单源最短路的方法：dijkstra算法（传送门）

对于迪杰斯特拉算法，他采用的是大贪心，但是这种贪心对于存在负权边的图就不好用了，因为负权边的存在，就会可能会影响最短路径的选择

这里就有了SPFA算法的用武之地！

SPFA的思路：

简单来说其实就是一个bfs

准备工作：一个用来存到源点的最短距离的dis数组、用来确定i点是否在对列中的vis数组，存图用的链式前向星、head数组

1. 存图，初始化
2. 将源点塞进对列，并对其进行初始化
3. 当对列飞空时，取队首，更新队首所有的边，进行松弛操作
4. 输出

公交线路

裸的SPFA板子题

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//typedef  long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, s, t, tot;
int x, y, z;
int dis[MAX];
int head[MAX];
bool vis[MAX];
struct ran{
    int to, next, val;
}tr[MAX];
queue<int>q;

void init(){
    mem(head, -1);
    mem(tr, 0);
    mem(vis, 0);
    mem(dis, inf);
    tot = 0;
}

void built(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].next = head[u];
    head[u] = tot;
}

void SPFA(){
    dis[s] = 0;vis[s] = 1;
    q.push(s);
    while (!q.empty()){
        int now = q.front();q.pop();
        vis[now] = 0;//一定记得及时更新vis
        for(int i = head[now]; i != -1; i = tr[i].next){
            int u = tr[i].to;
            if(dis[u] > dis[now] + tr[i].val){
                dis[u] = dis[now] + tr[i].val;
                if(!vis[u]){
                    q.push(u);
                    vis[u] = 1;//更新vis
                }
            }
        }
    }
    if(dis[t] == inf)cout<<-1<<endl;
    else cout<<dis[t]<<endl;
}

int main(){
    io;
    init();
    cin>>n>>m>>s>>t;
    for(int i = 1; i <= m; ++i){
        cin>>x>>y>>z;
        built(x, y, z);
        built(y, x, z);
    }
    SPFA();
    return 0;
}