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

Copy

样例输出1

Copy

限制

Test5 5秒
其余 1秒

提示

无聊的题，通过率我见过最低的题

很多坑，可能是不连通图

第一次T了，因为傻傻的跑了N次求最短路的SPFA ，

然后又W了，被WHW学长坑了~~~

之后就——》》比较喜欢用DFS判负环— 可以将两个SPFA和在一起但是太麻烦懒得改了~~~

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int M(+);

 const int N(+);

 const int INF(1e8);

 int n,m,s,u,v,w;

 int head[M],sumedge;

 struct Edge

 {

     int v,w,next;

     Edge(int v=,int next=,int w=):

         v(v),next(next),w(w) {}

 }edge[M];

 void ins(int u,int v,int w)

 {

     edge[++sumedge]=Edge(v,head[u],w);

     head[u]=sumedge;

 }

 long long dis[N];

 int if_ring,vis[N];

 void SPFAring(int pre)

 {

     if(if_ring) return ;

     vis[pre]=;

     for(int i=head[pre];i;i=edge[i].next)

     {

         int to=edge[i].v;

         if(dis[to]>dis[pre]+edge[i].w)

         {

             if(vis[to]||if_ring)

             {

                 if_ring=;

                 break ;

             }

             dis[to]=dis[pre]+edge[i].w;

             SPFAring(to);

         }

     }

     vis[pre]=;

 }

 void SPFAdist(int s)

 {

     queue<int>que;

     que.push(s);

     vis[s]=;

     dis[s]=;

     while(!que.empty())

     {

         u=que.front();que.pop();vis[u]=;

         for(int i=head[u];i;i=edge[i].next)

         {

             v=edge[i].v;

             if(dis[v]>dis[u]+edge[i].w)

             {

                 dis[v]=dis[u]+edge[i].w;

                 if(!vis[v]) que.push(v),vis[v]=;

             }

         }

     }

 }

 int if_,ch;

 void read(int &x)

 {

     x=;if_=;ch=getchar();

     for(;ch>''||ch<'';ch=getchar())

         if(ch=='-') if_=;

     for(;ch<=''&&ch>='';ch=getchar())

         x=x*+ch-'';

     if(if_) x=(~x)+;

 }

 int main()

 {

     read(n);read(m);read(s);

     for(;m;m--)

     {

         read(u);read(v);read(w);

         ins(u,v,w);

     }

     for(int i=;i<=n;i++)

     {

         SPFAring(i);

         if(if_ring)

         {

             printf("-1\n");

             return ;

         }

     }

     for(int j=;j<=n;j++)

     {

         dis[j]=INF;

         vis[j]=;

     }

     SPFAdist(s);

     for(int i=;i<=n;i++)

     {

         if(i==s)

         {

             printf("0\n");

             continue;

         }

         if(dis[i]>=INF) printf("NoPath\n");

         else printf("%lld\n",dis[i]);

     }

     return ;

 }

巴特西

Vijos——T1053 Easy sssp

https://vijos.org/p/1053

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

提示

最新文章

热门文章