SPFA算法模版，求单源最短路，可以有负环

算法优点：
1.时间复杂度比普通的Dijkstra和floyd低
2.能够计算负权图问题
3.能够判断是否有负环

针对输入和输出的不同分为多个模版，虽然这些东西都是可以随时调的。

第一个模版 ：
输入：先输入点，后输入边，再输入查询个数
例题链接：https://ac.nowcoder.com/acm/contest/1870/B

/*少说话，多做事*/
/*用这个模版的时候记得不同题目要改M和结构体a的大小*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define inf 0x3f3f3f3f
/*m,n-》 n个城市，m条边*/

const int M=50005;
struct sss
{
    ll v; //终点
    ll w; //边的权值
    ll next;
}a[1000002];

ll head[M]; //head存储的是以i为起点，最后输入的那个编号

ll vis[M],ven[M],nums[M]; //SPFS数组，vis记录最短路，ven记录是否在队列，nums记录入队次数
ll cnt=0; //链式前向星数组

void add(ll u,ll v,ll w)//链式前向星，加入节点
{
    a[cnt].v=v;
    a[cnt].w=w;
    a[cnt].next=head[u];
    head[u]=cnt++;
}

bool SPFA(int s,ll n)   //从s点开始出发，一共n条边
{
    queue <ll> q;
    vis[s]=0; //初始化距离
    ven[s]=1;
    q.push(s);
    while(!q.empty())
    {
        ll x=q.front(); //以x点为翘板
        q.pop();    //出队
        ven[x]=0;   //不在队列中
        nums[x]++;  //记录加入次数
        for(ll i=head[x]; i!=-1; i=a[i].next) //遍历与x节点连通的点
        {
            ll y=a[i].v;                //y是这条边的终点，以x为翘板，看初始点距离y点的距离可不可以更新
            if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > （初始点距离x的距离+i这条边的权值） ——> 更新
            {
                vis[y] = vis[x] + a[i].w;
                if(ven[y]==0) //由于更新了节点，所以后续以这个为基础的最短路，也要更新下，所以如果在队列就不用加入，不在的话加入更新后续节点
                {
                    q.push(y);
                    ven[y]=1; //加入队列
//                    nums[y]++;//记录加入次数
                    if(nums[y]>=n) return false; //如果这个点加入超过n次，说明存在负圈，直接返回
                }
            }
        }
    }
    return true;
}

void init()
{
    cnt=0;
    memset(vis,inf,sizeof(vis));  //设s点到其余各个点的距离都是最大值
    memset(head,-1,sizeof(head));   //链式向前星里面的head数组初始化为-1
    memset(nums,0,sizeof(nums));
    memset(ven, 0, sizeof(ven));
}

int main()
{
    ll n,m,b;
    /*m是边数，n是点数，B为最后判断个数*/
    while(cin >> m >> n >> b) //m为初始的点的个数,n为边数 （先输入点，后输入边）,b为最后查询个数
    {
        init();
        for(ll i=0;i<n;i++)
        {
            ll x,y,k;
            cin >> x >> y >> k;
            add(x, y, k);
            add(y, x, k);  //添加双向边
        }
        SPFA(1, n);
        for (int i=1;i<=b;i++)
        {
            int x,y;
            cin >> x >> y;
            cout << vis[x] + vis[y] << endl;
        }

    }
    return 0;
}

第二个模版：

输入：先输入边(n)，后输入点(m)
后面输入n条边（一条边三个数据），输出vis[m]

例题：SDNU 1223spfa判负环：http://www.acmicpc.sdnu.edu.cn/problem/show/1223

/*少说话，多做事*/
/*用这个模版的时候记得不同题目要改M和结构体a的大小*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define inf 0x3f3f3f3f
/*m,n-》 n个城市，m条边*/

const int M=50005;
struct sss
{
    ll v; //终点
    ll w; //边的权值
    ll next;
}a[1000002];

ll head[M]; //head存储的是以i为起点，最后输入的那个编号

ll vis[M],ven[M],nums[M]; //SPFS数组，vis记录最短路，ven记录是否在队列，nums记录入队次数
ll cnt=0; //链式前向星数组

void add(ll u,ll v,ll w)//链式前向星，加入节点
{
    a[cnt].v=v;
    a[cnt].w=w;
    a[cnt].next=head[u];
    head[u]=cnt++;
}

bool SPFA(int s,ll n)   //从s点开始出发，一共n条边
{
    queue <ll> q;
    vis[s]=0; //初始化距离
    ven[s]=1;
    q.push(s);
    while(!q.empty())
    {
        ll x=q.front(); //以x点为翘板
        q.pop();    //出队
        ven[x]=0;   //不在队列中
        nums[x]++;  //记录加入次数
        for(ll i=head[x]; i!=-1; i=a[i].next) //遍历与x节点连通的点
        {
            ll y=a[i].v;                //y是这条边的终点，以x为翘板，看初始点距离y点的距离可不可以更新
            if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > （初始点距离x的距离+i这条边的权值） ——> 更新
            {
                vis[y] = vis[x] + a[i].w;
                if(ven[y]==0) //由于更新了节点，所以后续以这个为基础的最短路，也要更新下，所以如果在队列就不用加入，不在的话加入更新后续节点
                {
                    q.push(y);
                    ven[y]=1; //加入队列
//                    nums[y]++;//记录加入次数
                    if(nums[y]>=n) return false; //如果这个点加入超过n次，说明存在负圈，直接返回
                }
            }
        }
    }
    return true;
}

void init()
{
    cnt=0;
    memset(vis,inf,sizeof(vis));  //设s点到其余各个点的距离都是最大值
    memset(head,-1,sizeof(head));   //链式向前星里面的head数组初始化为-1
    memset(nums,0,sizeof(nums));
    memset(ven, 0, sizeof(ven));
}
  int main()
{
    ll n,m;
    /*m是边数，n是点数，B为最后判断个数*/
    while(cin >> n >> m) //m为初始的点的个数,n为边数 （先输入边，后输入点）
    {
        init();
        for(ll i=0;i<n;i++)
        {
            ll x,y,k;
            cin >> x >> y >> k;
            add(x, y, k);
            add(y, x, k);  //添加双向边
        }
        /*以哪个点为初始点、一共有多少条边*/
        if(SPFA(1, n)) cout << vis[m] << endl;
        else cout << "IMPOSSIBLE!" << endl;
    }
    return 0;
}