UVa 558 Wormholes / Bellman-Ford

有个人要回到过去看大爆炸 就判断有没有负环 有负环就possible

Bellman-Ford 或者SPFA判断负环

#include 
  
   
struct node
{
	int s;
	int e;
	int w;
}a[2010];
int n,m;
int dis[1010];

bool BF()
{
	int i,j,k;
	int x,y,z;
	for(i = 0;i < n; i++)
		dis[i] = 999999999;
	dis[0] = 0;
	for(i = 0;i < n-1; i++)
	{
		for(j = 0;j < m; j++)
		{
			x = a[j].s;
			y = a[j].e;
			z = a[j].w;
			if(dis[y] > dis[x] + z)
				dis[y] = dis[x] + z;
		}
	}
	for(j = 0;j < m; j++)// 如果松弛了n-1次还能松弛 说明有负环 
	{
		x = a[j].s;
		y = a[j].e;
		z = a[j].w;
		if(dis[y] > dis[x] + z)
		{
			return false;
		}
	}
	return true; 
}
int main()
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		for(i = 0;i < m; i++)
			scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].w);
		if(!BF())
		{
			puts("possible");
		}
		else
		{
			puts("not possible");
		}
	}
	return 0;
}
  

下面是SPFA

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int MAX = 1010; struct node { int e; int w; }; int n,m; int dis[MAX]; int cnt[MAX]; bool vis[MAX]; vector 
      
        a[MAX]; bool SPFA() { int i; queue 
       
         q; memset(vis,false,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(i = 0;i < n; i++) dis[i] = 999999999; dis[0] = 0; q.push(0); while(!q.empty()) { int x = q.front(); q.pop(); vis[x] = false; int len = a[x].size(); for(i = 0; i < len; i++) { node t = a[x][i]; if(dis[t.e] > dis[x] + t.w) { dis[t.e] = dis[x] + t.w; if(!vis[t.e]) { q.push(t.e); vis[t.e] = true; cnt[t.e]++; if(cnt[t.e] > n) return false; } } } } return true; } int main() { int t,i,x,y,z; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); for(i = 0;i < n; i++) a[i].clear(); while(m--) { scanf("%d %d %d",&x,&y,&z); a[x].push_back((node){y,z}); } if(!SPFA()) puts("possible"); else puts("not possible"); } return 0; }