POJ 3259 Wormholes Bellman题解

版权声明：本文作者靖心，靖空间地址：http://blog.csdn.net/kenden23/。未经本作者同意不得转载。https://blog.csdn.net/kenden23/article/details/37737817

本题就是须要检查有没有负环存在于路径中，使用Bellman Ford算法能够检查是否有负环存在。

算法非常easy，就是在Bellman Ford后面添加一个循环推断就能够了。

题目故事非常奇怪，小心读题。

#include <stdio.h>

#include <string.h>

#include <limits.h>

const int MAX_N = 501;

const int MAX_M = 2501;

const int MAX_W = 201;

struct Edge

{

	int src, des, wei;

	//Edge(int s, int d, int w) : src(s), des(d), wei(w) {}

};

Edge edge[(MAX_M<<1)+MAX_W];

int dist[MAX_N];

int N, M, W, F;

bool cycleBellmanFord()

{

	for (int i = 1; i <= N; i++) dist[i] = INT_MAX;

	dist[1] = 0;

	for (int i = 1; i < N; i++)

	{

		bool seperate = true;

		for (int j = 0; j < (M<<1)+W; j++)

		{

			if (dist[edge[j].src] != INT_MAX &&

				dist[edge[j].src]+edge[j].wei < dist[edge[j].des])

			{

				dist[edge[j].des] = dist[edge[j].src]+edge[j].wei;

				seperate = false;

			}

		}

		if (seperate) break;

	}

	for (int j = 0; j < (M<<1)+W; j++)

	{

		if ( dist[edge[j].src] != INT_MAX &&

			dist[edge[j].src]+edge[j].wei < dist[edge[j].des]) return true;

	}

	return false;

}

int main()

{

	scanf("%d", &F);

	while (F--)

	{

		scanf("%d %d %d", &N, &M, &W);

		int i = 0;

		for ( ; i < (M<<1); i++)

		{

			scanf("%d %d %d", &edge[i].src, &edge[i].des, &edge[i].wei);

			i++;

			edge[i].des = edge[i-1].src;

			edge[i].src = edge[i-1].des;

			edge[i].wei = edge[i-1].wei;

		}

		for ( ; i < (M<<1)+W; i++)

		{

			scanf("%d %d %d", &edge[i].src, &edge[i].des, &edge[i].wei);

			edge[i].wei = -edge[i].wei;

		}

		if (cycleBellmanFord()) puts("YES");

		else puts("NO");

	}

	return 0;

}