[백준 BoJ] 1219 - 오민식의 고민

// https://www.acmicpc.net/problem/1219
// 오민식의 고민

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int N, M, from, to, INF = -999999999;
long long minCost[51];
int map[51];
bool visited[51], Geecheck[51];
bool check = false;
vector<vector<pair<int, int>>> Edge;
void bellman(int start) {
	fill(minCost, minCost + N + 1, INF);
	minCost[start] = map[start];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int current = j;
			for (auto e : Edge[j]) {
				int next = e.first;
				int cost = e.second;
				long long nextCost = cost + minCost[current] + map[next];
				if (minCost[current] != INF && minCost[next] < nextCost) {
					minCost[next] = nextCost;
					if (i == N - 1) Geecheck[j] = true;
				}
			}
		}
	}
}
void bfs() {
	queue<int> q;
	for (int i = 0; i < N; i++) {
		if (Geecheck[i]) {
			visited[i] = true;
			q.push(i);
		}
	}
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		if (current == to) {
			check = true;
			break;
		}

		for (auto e : Edge[current]) {
			int next = e.first;
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> from >> to >> M;
	Edge.resize(N);
	for (int i = 0; i < M; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		Edge[x].push_back(make_pair(y, -cost));
	}
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}
	
	bellman(from);
	bfs();

	if (minCost[to] == INF) cout << "gg";
	else {
		if (check) cout << "Gee";
		else cout << minCost[to];
	}

}

4 0 3 4
0 1 0
0 3 5
1 2 0
2 1 0
0 5 5 10

결과 값 : 5

위의 예시를 입력하면 5가 나와야 하지만 Gee를 출력한다. 도착지점에는 사이클이 돌지 않지만 다른 지점에서 사이클이 돌기 때문에 Gee라는 결과 값이 나옴. 사이클 판단 부분에서 Geecheck 배열에 담아준 뒤 해당 부분부터 bfs를 돌아 자기 자신으로 돌아온다면 돈을 무한으로 얻을 수 있는 사이클이 있다고 판단.

반례 참고 : https://txegg.tistory.com/128

[BOJ] 1219. 오민식의 고민