【模版】SPFA求最短路

题目测试：P4779 【模板】单源最短路径（标准版）

写在前面

如若用SPFA判断是否有负环
则相较于模版增加以下代码：

int cnt[MAXN];	//+
int SPFA(int s){	//void->int
    memset(cnt, 0, sizeof(cnt));	//+
    ...
		    if (!vis[e.to]){
	            ...
	            if (++cnt[e.to] > n) return 0;	//+
	            //当存在一个点入队大于等于n次，则有负环
	        }
	return 1;	//+
}

代码

//---------使用模版前言---------
//注意顶点数MAXN的值 注意极大数据inf的值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <algorithm>
#include <vector>
#define MAXN 300010     //最大顶点数 注意依题修改大小
#define inf 0x3f3f3f3f   //极大数据 10^9数量级
using namespace std;
typedef pair<int, int> info;    //存放当前点及从源点到当前点的最短路径的信息
priority_queue<info, vector<info>, greater<info> > Q;
//优先队列实现将已确定最短路径的点放入队列 小顶堆实现堆优化
struct edge{    //定义弧信息
    int to;     //弧指向的点
    int weight;     //弧的权重
    edge(int t, int w): to(t), weight(w){}  //弧的初始化
};
vector<edge> G[MAXN];   //存放当前点出发的每一条弧的信息
int n, m, s;    //点 弧 源点
int dis[MAXN];  //从源点到当前点的最短路径(迪杰斯特拉跑完之前不一定是最终解)
int vis[MAXN];  //该数组用于标记当前点是否已访问过 起到优化作用
void SPFA(int s){   //s为源点，使用SPFA查找源点到其他任意点的最短路径
    memset(vis, 0, sizeof(vis));
    //每跑一次算法重置访问标记数组 跑一次算法可得出一个源点到其他任意点的最短路径
    for (int i = 1; i <= n; i++) dis[i] = inf;
    //初始化源点到任意其他点最短路径无穷大 注意从零开始还是从一开始
    dis[s] = 0; //源点到源点最短路径为0
    vis[s] = 1; //标记源点
    Q.push(make_pair(0, s));    //将源点放入队列
    while (!Q.empty()){ //结束条件为队列里无未确定最短路径点
        info u = Q.top();
        Q.pop();    //取出并去除队头元素
        int x = u.second;   //当前点编号
        vis[x] = 0; //使当前点处于未标记状态 不是很懂 SPFA思想
        for (int i = 0; i < G[x].size(); i++){  //遍历从x点出发的所有弧
            edge e = G[x][i];   //从x点出发的第i条弧
            if (dis[e.to] > dis[x] + e.weight){
                //若经过x点的松弛使得从源点到弧尾指向的点的最短路径更短 则更新最短路径
                dis[e.to] = dis[x] + e.weight;
                if (!vis[e.to]){    //如果目标点未访问
                    Q.push(make_pair(dis[e.to], e.to));
                    //将已确定最短路径的点放入队列
                    vis[e.to] = 1;  //标记该点已访问
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &s);    //点 弧 源点
    int from, to, weight;   //弧的起点 终点 权重
    for (int i = 1; i <= m; i++){
        scanf("%d%d%d", &from, &to, &weight);
        edge in(to, weight);
        G[from].push_back(in);  //往图中加入所有已知弧的信息
    }
    SPFA(s);    //算法实施
    for (int i = 1; i < n; i++) printf("%d ", dis[i]);
    printf("%d\n", dis[n]);     //规范输出无多余空格
    //输出从源点到其他所有点的最短路径
    return 0;
}