2 条题解

  • 2
    @ 2022-11-6 16:41:12
    #include <queue>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define LL long long
    const int N = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    LL head[N], to[N], w[N], idx, ne[N];
    LL dis[N], vis[N], num[N];
    inline void add(int x, int y , int z)
    {
    	to[++idx] = y;
    	w[idx] = z;
    	ne[idx] = head[x];
    	head[x] = idx;
    }
    LL n, m, s;
    bool spfa(int k)
    {
    	memset(num , 0, sizeof(num));
    	memset(vis , 0, sizeof(vis));
    	memset(dis , 0x3f, sizeof(dis));
    	stack<int> p;//先进后出
    	//可能会有负环点进队列时,马上就出队列了
    	//所以用栈
    	p.push(k); 
    	vis[k] = 1;
    	dis[k] = 0;
    	num[k]++;
    	while(!p.empty())
    	{
    		int t = p.top();
    		p.pop();
    		vis[t] = 0;
    		for(int i = head[t]; i ; i = ne[i])
    		{
    			if(dis[to[i]] > w[i] + dis[t])
    			{
    				dis[to[i]] = w[i] + dis[t];
    				if(!vis[to[i]])
    				{
    					p.push(to[i]);
    					num[to[i]]++;
    					vis[to[i]] = 1;
    					if(num[to[i]] >= n)
    						return true;
    				}
    			}
    		}
    	}	
    	return false;
    }
    int main()
    {
    	scanf("%lld%lld%lld", &n, &m, &s);
    	for(LL i = 0, x, z, y; i < m; i++)
    	{
    		scanf("%lld%lld%lld", &x, &y, &z);
    		add(x, y, z);
    	}
    	//超级原点 
    	int k = n + 1;
    	for(int i = 1; i <= n; i++)
    		add(k, i, 0);
    	//如果1 2 3联通,而4 5是负环,先判断有无负环 
    	if(spfa(k))
    	{ 
    		//有,输出-1
    		cout << "-1" << endl;
    	}
    	//没有,进行运算 
    	else 
    	{
    		spfa(s);
    		for(int i = 1; i <= n; i++)
    		{
    			if(dis[i] >= INF)
    			{ 
    				puts("NoPath");
    				//不联通 
    			}
    			else
    			{
    				printf("%lld\n",dis[i]);
    				//输出值 
    			}
    		}
    	}
    	return 0;
    }
    
    • 1
      @ 2021-11-13 17:13:04
      /*****************************************
      备注:
      ******************************************/
      #include <queue>
      #include <math.h>
      #include <stack>
      #include <stdio.h>
      #include <iostream>
      #include <vector>
      #include <iomanip>
      #include <string.h>
      #include <algorithm>
      using namespace std;
      #define LL long long
      const int N = 1e6 + 10;
      const int INF = 0x3f3f3f3f;
      LL head[N] , to[N] , w[N] , idx,ne[N];
      LL dis[N] , vis[N], num[N] ,st[N] ,top = 0;
      inline void add(int x, int y , int z)
      {
      	to[++idx] = y;
      	w[idx] = z;
      	ne[idx] = head[x];
      	head[x] = idx;
      }
      LL n , m , s;
      bool spfa(int k)
      {
      	memset(num , 0 ,sizeof(num));
      	memset(vis , 0 ,sizeof(vis));
      	memset(dis , 0x3f ,sizeof(dis));
      	st[++top] = k;
      	vis[k] = 1;
      	dis[k] = 0;
      	num[k]++;
      	while(top > 0)
      	{
      		int t = st[top--];
      		vis[t] = 0;
      		for(int i = head[t] ; i ; i = ne[i])
      		{
      			if(dis[to[i]] > w[i] + dis[t])
      			{
      				dis[to[i]] = w[i] + dis[t];
      				if(!vis[to[i]])
      				{
      					st[++top] = to[i];
      					num[to[i]]++;
      					vis[to[i]] = 1;
      					if(num[to[i]] >= n)
      						return true;
      				}
      			}
      		}
      	}	
      	return false;
      }
      int main()
      {
      	scanf("%lld%lld%lld",&n,&m,&s);
      	for(LL i =0,x,z,y  ; i < m ; i++)
      	{
      		scanf("%lld%lld%lld",&x,&y,&z);
      		add(x,y,z);
      	}
      	int k = n+1;
      	for(int i = 1; i <= n ; i++)
      		add(k , i , 0);
      	if(spfa(k))
      		cout << -1;
      	else 
      	{
      		spfa(s);
      		for(int i = 1 ;  i <= n ; i++)
      		{
      
      			if(dis[i] >= INF)
      				puts("NoPath");
      			else 
      				printf("%lld\n",dis[i]);
      		}
      	}
      
      	return 0;
      }
      
      
      
      
      
      
      
      • 1

      信息

      ID
      420
      时间
      1000ms
      内存
      512MiB
      难度
      8
      标签
      递交数
      306
      已通过
      55
      上传者