Easy sssp

时间限制: 1 Sec 内存限制: 128 MB
提交: 103 解决:
20
[提交][状态][讨论版]

题目描述

输入数据给出一个有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的最短路的长度.

样例输入

样例输出

提示

做这道题时, 你不必为超时担心, 不必为不会算法担心, 但是如此“简单”的题目, 你究竟能ac么?

题解：这是一道spfa的题目吧，考点是spfa的应用和spfa判断负权回路的问题，每个块都判断一次，若其中有一个块存在负权回路，则直接输出NoPath；如果不存在，则输出最短路即可。

　　　 spfa判断负环应该都知道吧，一个点如果进栈n次则存在负环。

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<string>

 #include<cstring> 

 using namespace std;

 const int MAXN=,MAXM=; 

 int num,first[MAXN],next[MAXM],arr[MAXM],cost[MAXM];

 int times[MAXN];

 int n,m,st;

 int p[MAXN];

 bool boo[MAXN],he[MAXN];

 long long dis[MAXN]; 

 void add(int u,int v,int z)

 {

     num++;

     next[num]=first[u];

     first[u]=num;

     arr[num]=v;

     cost[num]=z;

 }

 void init()

 {

     memset(he,,sizeof(he));

     memset(times,,sizeof(times));

     memset(boo,,sizeof(boo));

     memset(next,,sizeof(next));

     memset(arr,,sizeof(arr));

     memset(cost,,sizeof(cost));

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

         first[i]=-;

     num=;

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

         dis[i]=;

     dis[st]=;

 }

 bool pan(int st)

 {

     int head=,tail=;

     p[tail]=st,boo[st]=;

     times[st]++; 

     while (head!=tail)

     {

         head=head%n+;

         int u=p[head],v;

         for (int i=first[u];i!=-;i=next[i])

         {

             v=arr[i];

             if (dis[u]+cost[i]<dis[v])

             {

                 dis[v]=dis[u]+cost[i];

                 if (boo[v]==)

                 {

                     times[v]++;

                     if (times[v]>=n)

                     {

                         return ;

                     }

                     boo[v]=;

                     tail=tail%n+;

                     p[tail]=v;

                 }

             }

         }

         boo[u]=;

     }

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

         if (dis[i]<) he[i]=;

     return ;

 }

 void solve(int st)

 {

     int head=,tail=;

     p[tail]=st,boo[st]=; 

     while (head!=tail)

     {

         head=head%n+;

         int u=p[head],v;

         for (int i=first[u];i!=-;i=next[i])

         {

             v=arr[i];

             if (dis[u]+cost[i]<dis[v])

             {

                 dis[v]=dis[u]+cost[i];

                 if (boo[v]==)

                 {

                     boo[v]=;

                     tail=tail%n+;

                     p[tail]=v;

                 }

             }

         }

         boo[u]=;

     }

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

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

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

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&st);

     init();  

     int x,y,z;

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

     {

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);

     }

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

         if (he[i]==)

         {

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

                 dis[i]=;

             dis[i]=;

             if (pan(i))

             {

                 printf("-1\n");

                 return ;

             }

             memset(boo,,sizeof(boo));

             memset(times,,sizeof(times));

         }

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

         dis[i]=;

     dis[st]=;

     solve(st);

 }

Easy sssp

Easy sssp

题目描述

输入

输出

样例输入

样例输出

提示

相关文章