easy sssp（spfa判断负环）

easy sssp

描述：
输入数据给出一个有N(2 <= N <= 1,000)个节点，M(M <= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.
输入格式：
第一行: 点数N(2 <= N <= 1,000), 边数M(M <= 100,000), 源点S(1 <= S <= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(-1,000,000 <= c <= 1,000,000)
输出格式：
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出NoPath;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度.

思路：
1、spfa判断负环：若一个点入队次数大于节点数，则存在负环。
2、有特殊情况，若存在两个环，s在正环中，但是另一个环是负环，这种情况要特殊处理，输出的是-1，但是处理不好会出现一堆NoPath。
3、读入优化，否则有一个点会超时！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=1010;
queue<int> q;
struct node
{
    int to;
    int w;
    int next;
}e[maxn*100];
int n,m,s,tot,head[maxn],in[maxn];
long long dis[maxn],dis1[maxn];
bool flag[maxn];
int init()
{
    int p=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        p=p*10+c-'0';
        c=getchar();
    }
    return p*f;
}
void edd_edge(int u,int v,int w)
{
    tot++;
    e[tot].to=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
}
void spfa(int x)
{
    dis[x]=0;
    flag[x]=1;
    in[x]++;
    q.push(x); 
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        flag[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                if(!flag[v])
                {
                    q.push(v);
                    flag[v]=1;
                    in[v]++;
                    if(in[v]>n)
                    {
                        cout<<-1;
                        exit(0);
                    }
                }
            }
        }
    }
}
void spfa1(int x)
{
    memset(in,0,sizeof(in));
    memset(flag,0,sizeof(flag));
    dis1[x]=0;
    flag[x]=1;
    in[x]++;
    q.push(x); 
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        flag[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis1[v]>dis1[u]+e[i].w)
            {
                dis1[v]=dis1[u]+e[i].w;
                if(!flag[v])
                {
                    q.push(v);
                    flag[v]=1;
                    in[v]++;
                    if(in[v]>n)
                    {
                        cout<<-1;
                        exit(0);
                    }
                }
            }
        }
    }
}
int main()
{
    int x,y,z;
    n=init();m=init();s=init();
    for(int i=1;i<=m;i++)
    {
        x=init();y=init();z=init();
        edd_edge(x,y,z);
    }
    for(int i=0;i<=n;i++)
    dis[i]=dis1[i]=maxn*maxn;
    spfa(s);
    for(int i=1;i<=n;i++)
    if(dis[i]==dis[0])
    spfa1(i);
    for(int i=1;i<=n;i++)
    {
        if(dis[i]!=maxn*maxn)
        cout<<dis[i]<<endl;
        else
        cout<<"NoPath"<<endl;
    }
    return 0;
}