Vijos1053 Easy sssp

题意

给一个有向图，如果有负权回路输出-1，否则输出从起点 $S$ 到各个点的最短路长度，如果不连通输出NoPath。

其中点数 $N\le 1000$ ，边数 $M\le 100000$ 。

题解

做法很显然，就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环，求最短路就顺便继续用，然后就很开心的被卡超时了。

正解就是用广搜 $spfa$ ，但我又不想删判负环的所以就写了两个。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to,w;
} edge[100005];
ll cnt,head[1005],n,m,s,a,b,c,dis[1005];
bool vis[1005];

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

bool spfa(ll x)
{
    if (vis[x]) return 0;
    vis[x]=1;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to,w=edge[i].w;
        if (dis[x]+w<dis[y])
        {
            dis[y]=dis[x]+w;
            if (vis[y] || spfa(y)) return vis[x]=0,1;
        }
    }
    return vis[x]=0,0;
}

inline bool check()
{
    memset(dis,0,sizeof(dis));
    for (ll i=1;i<=n;i++)
    {
        if (!spfa(i)) continue;
        return 1;
    }
    return 0;
}

inline void bfs_spfa()
{
    for (ll i=1;i<=n;i++) dis[i]=1e18;
    dis[s]=0;
    queue <ll> q;
    q.push(s);
    while (!q.empty())
    {
        ll x=q.front(); q.pop();
        vis[x]=0;
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                if (vis[y]) continue;
                vis[y]=1;
                q.push(y);
            }
        }
    }
}

int main()
{
    n=read(); m=read(); s=read();
    for (ll i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        if (a==b) continue;
        add(a,b,c);
    }
    if (check()) printf("-1");
    else
    {
        bfs_spfa();
        for (ll i=1;i<=n;i++) printf((dis[i]>=1e18) ? "NoPath\n" : "%lld\n",dis[i]);
    }
    return 0;
}