首页 > 代码库 > vijos1053Easy sssp

vijos1053Easy sssp

2024-07-18 07:16:27   221人阅读

                                         P1053Easy 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的最短路的长度.

样例输入

6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

样例输出

0
6
4
-3
-2
7

题解：

本来只是一个简单的spfa判负环，结果出题人故意从中作怪。卡时+各种奇葩数据。。。

第三个数据1单独成一个连通块，另一个连通块内有负环

第二个数据1单独成一个连通块，另一个连通块内无负环

只有以1为起点，rand为起点算两次了

最后还被cin cout卡掉了

又去网上找scanf和printf的资料，太乱了索性抄了个读入优化

代码：

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define maxn 5000+100 7 #define maxm 100000+1000 8 #define inf 1000000000 9 using namespace std;10 inline int read()11 {12     int x=0,f=1;char ch=getchar();13     while(ch<‘0‘||ch>‘9‘){if(ch=‘-‘)f=-1;ch=getchar();}14     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f;16 }17 struct edge{int go,next,w;}e[2*maxm];18 int n,m,k,s,tot,q[maxn],d[maxn],c[maxn],head[maxn],d2[maxn];19 bool v[maxn];20 void insert(int x,int y,int z)21 {22     e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;23 }24 bool spfa()25 {26     for(int i=1;i<=n;++i) d[i]=inf;27     memset(v,0,sizeof(v));28     int l=0,r=1,x,y;q[1]=s;d[s]=0;c[s]=0;29     while(l!=r)30     {31         //cout<<l<<‘ ‘<<r<<endl;32         x=q[++l];if(l==maxn)l=0;v[x]=0;33         for(int i=head[x];i;i=e[i].next)34          if(d[x]+e[i].w<d[y=e[i].go])35          {36              d[y]=d[x]+e[i].w;37              c[y]=c[x]+1;if(c[y]>n)return 0;38              if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}39          }40     }41     return 1;42 }43 int main()44 {45     freopen("input.txt","r",stdin);46     freopen("output.txt","w",stdout);47     n=read();m=read();s=read();int x,y,z;48     for(int i=1;i<=m;i++){x=read();y=read();z=read();insert(x,y,z);}49     if(!spfa())printf("-1\n");else50     {51         for(int i=1;i<=n;i++)d2[i]=d[i];52         s=rand();53         if(!spfa()){printf("-1\n");return 0;};54         for(int i=1;i<=n;i++)if(d2[i]!=inf)printf("%d\n",d2[i]);else printf("NoPath\n");55     }56     return 0;   57 }
View Code

 


联系
我们