TIMETRIP

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_V 100
#define INF 99999

using namespace std;

// first - vertex, second - cost
vector<pair<int, int>> adj[MAX_V];
bool reachable[MAX_V][MAX_V];

void floyd(int vCnt);
int bellman2(int src, int target, int vCnt);

int main()
{
	int caseNum;

	cin >> caseNum;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		for (int i = 0; i < MAX_V; i++) { adj[i].clear(); }

		int g, w;
		cin >> g >> w;

		int a, b, d;
		for (int wIter = 0; wIter < w; wIter++)
		{
			cin >> a >> b >> d;

			adj[a].push_back(make_pair(b, d));
		}

		floyd(g);

		int distance = bellman2(0, 1, g);
		
		// reverse input
		for (int here = 0; here < g; here++)
			for (int i = 0; i < adj[here].size(); i++)
				adj[here][i].second *= -1;

		floyd(g);

		int reverse_distance = bellman2(0, 1, g);

		if (distance == INF || distance == -INF)
		{
			cout << "UNREACHABLE" << endl;
		}
		else
		{
			cout << distance << " ";

			if (reverse_distance == INF || reverse_distance == -INF)
			{
				cout << "INFINITY" << endl;
			}
			else
			{
				cout << reverse_distance << endl;
			}
		}
	}
}

int bellman2(int src, int target, int vCnt)
{
	vector<int> upper(MAX_V, INF);
	upper[src] = 0;

	for (int iter = 0; iter < vCnt - 1; iter++)
	{
		for (int here = 0; here < vCnt; here++)
		{
			for (int i = 0; i < adj[here].size(); i++)
			{
				int there = adj[here][i].first;
				int cost = adj[here][i].second;

				upper[there] = min(upper[here] + cost, upper[there]);
			}
		}
	}

	for (int here = 0; here < vCnt; here++)
	{
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			int cost = adj[here][i].second;

			if (upper[here] + cost < upper[there]) // exist negative cycle
			{
				if (reachable[src][here] && reachable[here][target])
				{
					return -INF;
				}
			}
		}
	}

	return upper[target];
}

void floyd(int vCnt)
{
	int tmpAdj[MAX_V][MAX_V];

	// Initialize
	for (int i = 0; i < vCnt; i++)
	{
		for (int j = 0; j < vCnt; j++)
		{
			if (i == j)
			{
				tmpAdj[i][j] = 0;
				continue;
			}

			tmpAdj[i][j] = INF;
		}
	}

	for (int here = 0; here < vCnt; here++)
	{
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			int cost = adj[here][i].second;

			tmpAdj[here][there] = cost;
		}
	}

	// floyd
	for (int k = 0; k < vCnt; k++)
	{
		for (int i = 0; i < vCnt; i++)
		{
			if (tmpAdj[i][k] == INF) continue;

			for (int j = 0; j < vCnt; j++)
			{
				tmpAdj[i][j] = min(tmpAdj[i][j], tmpAdj[i][k] + tmpAdj[k][j]);
			}
		}
	}

	// set reachable[][]
	for (int i = 0; i < vCnt; i++)
		for (int j = 0; j < vCnt; j++)
			reachable[i][j] = tmpAdj[i][j] == INF ? false : true;
}

TimetripInput.txt

0.00MB

TimetripOutput.txt

0.00MB

 

if (reachable[src][here] && reachable[here][target])
{
    return -INF;
}

 

이 부분이 잘 이해가 가지 않는다. src -> target 으로 가는 경로에 음수 cost 를 가진 here 가 있다는 사실 하나만으로 어떻게 음수 사이클에 빠질 수 있다고 결론지을 수 있지? src -> here -> target 의 경로에서 here->there로 가는 cost가 음수값이라고 할 때, there->here 로 오는 cost가 이 음수값보다 절대값이 큰 양수 값이라면 음수 사이클이라고 할 수가 있을까? 또 하나, here->there로 가는 경로가 있다고 해서 there->here 로 가는 경로가 있다는 보장이 없다. 그래서 src->target 의 경로 중 음수 사이클이 있다는 보장을 확실히 하려면 here->there의 음수 cost만 체크할 게 아니라 "there->here의 reachable 여부" 와 "here->there->here의 결론적인 cost값이 음수인지 양수인지 여부"도 함께 체크해야 하는 것 아닐까? 책에는 이 부분에 대한 설명이 따로 없어서 일단 의문점을 글로 남겨본다.