Easy sssp(vijos 1053)

描述

输入数据给出一个有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

样例输入1[复制]

样例输出1[复制]

限制

Test5 5秒
其余 1秒

/*
  一个水题，水了一下午了才水过去，陷阱太多了
  这不是普通的spfa的模板，因为有些点可能起点没有连通，但是却构成了环，应该输出-1，
  却输出了一堆 NoPath，所以应该设一个inp数组，记录某个点有没有出现过，然后把所有
  没有出现过的点再spfa一遍。 
*/
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define N 1010
#define M 100010
#define INF 10000000
#define LL long long
using namespace std;
int head[N],vis[N],num[N],inp[N],n,m,flag;
LL dis[N],dis1[N];
struct node
{
    int v,pre,t;
};node e[M];
queue<int> q;
int read()
{
    char c=getchar();int num=0,flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    return num*flag;
}
void add(int cnt,int x,int y,int z)
{
    e[cnt].v=y;
    e[cnt].t=z;
    e[cnt].pre=head[x];
    head[x]=cnt;
}
void spfa(int s,LL d[])
{
    while(!q.empty())q.pop();
    vis[s]=1;
    inp[s]=1;
    q.push(s);
    d[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].pre)
        {
            int y=e[i].v;
            if(d[y]>d[x]+(LL)e[i].t)
            {
                d[y]=d[x]+(LL)e[i].t;
                if(!vis[y])
                {
                    inp[y]=1;
                    vis[y]=1;
                    num[y]++;
                    q.push(y);
                    if(num[y]>=n||d[s]<0)
                    {
                        flag=1;
                        return;
                    }
                }
            }
        }
    }
}
int main()
{
    n=read();m=read();int s=read();
    for(int i=0;i<=n;i++)dis[i]=INF;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add(i,x,y,z);
    }
    spfa(s,dis);
    for(int i=1;i<=n;i++)
      if(!inp[i])
      {
          if(flag){printf("-1");return 0;}
          spfa(i,dis1);
      }
    if(flag){printf("-1");return 0;}
    for(int i=1;i<=n;i++)
      if(dis[i]<dis[0])cout<<dis[i]<<endl;
      else printf("NoPath
");
    return 0;
}

View Code