简单单源最短路径问题

本题目和模板题最大的区别是，不断要判断是否存在负环，还需要判断源点到各个点的最短路径

1.判断负环

根据抽屉定理，如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环

根据spfa算法的更新思路，就是一旦出现负环，就会在负环上不断绕圈圈，进而绕出cnt[i] > n的效果，因此我们可以使用一个$cnt$数组来维护当前这个点之前走过多少个点。

但是判断负环的题目一般都会挖一个坑，即可能存在从源点走不到的负环，进而导致判断不出负环，所以如果要判断是否存在负环，我们必须要将所有的点入队，然后遍历一遍看是否存在环

2.求最短路径

最短路径的求法就是裸spfa算法

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e6 + 10;

int n, m, s;
int h[N],ne[N],e[N],w[N],idx;
int dist[N],cnt[N];
bool v[N];
queue<int> q;

void add(int a,int b,int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    v[s] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop();
        v[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];
                cnt[j] = cnt[t] + 1;
                //如果cnt[j]大于n，则说明存在负环
                if(cnt[j] > n) return -1;
                if(!v[j])
                {
                    v[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return 1;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(cnt, 0, sizeof cnt);
    scanf("%d%d%d",&n,&m,&s);
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    //1.将所有点入队，判断是否存在负环
    for(int i = 1;i <= n; i ++)
        q.push(i);

    int t = spfa();

    if(t == -1)
        cout<<-1;
    else
    {
        //2.如果不存在负环，则在用一次spfa求最短路径
        q.push(s);
        t = spfa();
        for(int i = 1; i <= n; i ++)
        {
            if(dist[i] > 0x3f3f3f3f / 2)    cout<<"NoPath"<<endl;
            else    cout<<dist[i]<<endl;
        }
    }

    return 0;
}