题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度

思路

一个普通的spfa
然后注意的是题目中给定了最大值！！！！！
O(KE)

#include <stdio.h>
#include <queue>
#include <iostream>
#define maxn 500001
#define INF 2147483647
using namespace std;
int l=0,s;
struct arr 
{ 
    long long x,y,w,next;   
};
long long x,y,z;
arr edge[maxn];
int ls[maxn];
long long state[maxn];
bool exits[maxn];
int spfa()
{
    long long i;
    queue <long long> t;
    t.push(s);
    state[s]=0;
    exits[s]=true;
    do
    {
        long long tt=t.front();
        t.pop();
        i=ls[tt];
        while (i!=0) 
        {
            if (state[edge[i].x]+edge[i].w<=state[edge[i].y])
            {
                state[edge[i].y]=state[edge[i].x]+edge[i].w;
                if (exits[edge[i].y]==false)
                {
                    t.push(edge[i].y);
                    exits[edge[i].y]=true;
                }
            }
            i=edge[i].next;
        }
        exits[tt]=false;
    }
    while (!t.empty());
}
int main()
{
    int j,k,n,m;
    scanf("%d%d%d",&n,&m,&s);
    for (int i=1;i<=m;i++)
    {
        l++;
        scanf("%lld%lld%lld",&x,&y,&z);
        edge[l].x=x; edge[l].y=y; edge[l].w=z; edge[l].next=ls[edge[l].x]; ls[edge[l].x]=l;
    }

    for (int i=1;i<maxn;i++)
        state[i]=INF;

    spfa();

    for (int i=1;i<=n;i++)
        printf("%lld ",state[i]);
}