POJ 3259 Wormholes

題意：
    FJ要找出是否能從某個起點出發，然後回到該起點但可以遇見出發時的自己，也就是時間和要<0。

• 題目N表示有幾個點
• M表示有M行，每行S,E,T三個數字表示S點到E點或E點到S點所需要的時間是T
• W表示有W行，每行S,E,T三個數字表示S點到E點所減少的時間T，也就是S到E你的時間總和會-T，注意這個是單向的，只有S點到E點

想法：

    本題換句話說就是找出是否有負環(negative cycle)，確認在所有路徑中是否存在一個cycle，使得一直走那個cycle時間總合會越來越小。

	#include <cstdio>
	using namespace std;
	#define Inf 99999999
	struct Edge{
	int x;
	int y;
	int Len;
	}E[3000];
	int Dis[1001];
	void Initial(const int &N);
	bool BellmanFord(const int &N, const int &M, const int &W);
	bool Relax(const Edge &E, bool Double);
	int main()
	{
	int Case, N, M, W;
	scanf("%d", &Case);
	while (Case--){
	scanf("%d %d %d", &N, &M, &W);
	Initial(N);
	for (int i = 0; i < M; ++i)
	scanf("%d %d %d", &E[i].x, &E[i].y, &E[i].Len);
	for (int i = M; i < M + W; ++i){
	scanf("%d %d %d", &E[i].x, &E[i].y, &E[i].Len);
	E[i].Len *= -1;
	}
	if (BellmanFord(N, M, W)) puts("NO");
	else puts("YES");
	}
	}
	void Initial(const int &N)
	{
	Dis[N] = 0;
	for (int i = 1; i < N; ++i)
	Dis[i] = Inf;
	}
	bool BellmanFord(const int &N, const int &M, const int &W)
	{
	for (int times = 0; times < N; ++times){
	bool NotOK = 0;
	for (int i = 0; i < M + W; ++i)
	if (Relax(E[i], i < M)) NotOK = 1;
	if (!NotOK) return true;
	}
	return false;
	}
	bool Relax(const Edge &E, bool Double)
	{
	bool change = 0;
	if (Dis[E.x] + E.Len < Dis[E.y]){
	Dis[E.y] = Dis[E.x] + E.Len;
	change = 1;
	}
	if (Double && Dis[E.y] + E.Len < Dis[E.x]){
	Dis[E.x] = Dis[E.y] + E.Len;
	change = 1;
	}
	return change;
	}

view raw [POJ] 3259 Wormholes.cpp hosted with ❤ by GitHub