[BOJ/Platinum 5] 백준 1219 오민식의 고민(C++)

문제 링크

https://www.acmicpc.net/problem/1219

 

문제

오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.

오민식은 고민에 빠졌다.

어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.

오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 하려고 한다. 이 최댓값을 구하는 프로그램을 작성하시오.

오민식이 버는 돈보다 쓰는 돈이 많다면, 도착 도시에 도착할 때 가지고 있는 돈의 액수가 음수가 될 수도 있다. 또, 같은 도시를 여러 번 방문할 수 있으며, 그 도시를 방문할 때마다 돈을 벌게 된다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러 번 이용할 수도 있다.

 

입력

첫째 줄에 도시의 수 N과 시작 도시, 도착 도시 그리고 교통 수단의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에는 교통 수단의 정보가 주어진다. 교통 수단의 정보는 “시작 끝 가격”과 같은 형식이다. 마지막 줄에는 오민식이 각 도시에서 벌 수 있는 돈의 최댓값이 0번 도시부터 차례대로 주어진다.

N과 M은 50보다 작거나 같고, 돈의 최댓값과 교통 수단의 가격은 1,000,000보다 작거나 같은 음이 아닌 정수이다.

 

출력

첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착했을 때 돈을 무한히 많이 가지고 있을 수 있다면 "Gee"를 출력한다.

 

예제 입력 1

5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
0 0 0 0 0

예제 출력 1

-32

예제 입력 2

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

예제 출력 2

Gee

예제 입력 3

3 0 2 3
0 1 10
1 0 10
2 1 10
1000 1000 47000

예제 출력 3

gg

예제 입력 4

2 0 1 2
0 1 1000
1 1 10
11 11

예제 출력 4

Gee

예제 입력 5

1 0 0 1
0 0 10
7

예제 출력 5

7

예제 입력 6

5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
8 10 20 1 100000

예제 출력 6

99988

 

알고리즘 분류

• 최단 거리 알고리즘

 

풀이

교통 수단을 이용할 때마다 지불할 비용(+)이 존재하고, 도착 지점에 방문할 시 얻는 비용(-)이 있기 때문에 최종적으로 음수의 비용을 가지는 교통 수단이 존재하므로 벨만-포드 알고리즘을 활용해야 한다.

벨만-포드 알고리즘에서는 가중치를 무한으로 늘릴 수 있는 음의 사이클을 찾을 수 있다. 그리고 오민식이 출발지에서 도착지까지 가면서 무한히 돈을 벌 수 있다면, 출발지와 도착지를 모두 포함하는 음의 사이클이 존재한다.

M개의 교통 수단을 N-1번 탐색하면서 각 도시를 방문했을 때 벌 수 있는 비용을 갱신한다. 그리고 마지막으로 M개의 교통 수단을 다시 탐색하며, 이 때 또 비용 갱신이 가능한 도시가 있다면 해당 도시는 음의 사이클에 포함된다.

근데 E번 도시가 음의 사이클이 포함된다고 끝이 아니고, S번 도시에서 E번 도시까지 도착할 수 있는지를 판단해야 한다. 따라서 음의 사이클에 포함되는 모든 도시를 큐에 push한다.

큐에 있는 도시들을 pop하면서, 다음으로 방문할 수 있는 도시들을 탐색하고 방문 처리하며 큐에 push하는 과정을 반복하면서 E번 도시까지 방문할 수 있음을 확인한다.

마지막으로, 경우에 따라 답을 다르게 출력한다.

• 오민식이 E번 도시를 방문할 수 없다면, 즉 E번 도시까지 가는 데 드는 비용이 무한대에서 갱신되지 않았다면 gg를 출력한다.
• 오민식이 E번 도시를 방문할 수 있고, E번 도시가 음의 사이클에 포함된다면 Gee를 출력한다.
• 오민식이 E번 도시를 방문할 수 있고, E번 도시가 음의 사이클에 포함되지는 않는다면 E번 도시까지 가는 데 드는 비용에서 -1을 곱한 값을 출력한다.
  • -1을 곱하는 이유는, 문제 풀이를 할 때는 지불할 비용이 양수고, 얻는 비용이 음수였는데, 실제로는 지불하는 비용이 음수이기 때문이다.

 

E번 도시가 실제로 음의 사이클에 포함되는지까지를 확인해야 하는데, 그걸 몰라서 검색을 해서 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 51
#define INF 1e18
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct EDGE {
	int U, V;
	LL W;
};

int N, S, E, M;
vector<EDGE> Edges;
LL Money[MAX], Dist[MAX];
queue<int> Q;
bool Visited[MAX];

void init() {
	for (int i = 0; i < MAX; i++) {
		Dist[i] = INF;
	}
}

void input() {
	cin >> N >> S >> E >> M;
	Edges.resize(M);
	for (int i = 0; i < M; i++) {
		cin >> Edges[i].U >> Edges[i].V >> Edges[i].W;
	}
	for (int i = 0; i < N; i++) {
		cin >> Money[i];
	}
}

void bellmanFord() {
	Dist[S] = -Money[S];

	for (int i = 0; i < (N - 1); i++) {
		for (int j = 0; j < M; j++) {
			int U = Edges[j].U;
			int V = Edges[j].V;
			LL W = Edges[j].W;

			if ((Dist[U] < INF) && (Dist[U] + W - Money[V] < Dist[V])) {
				Dist[V] = Dist[U] + W - Money[V];
			}
		}
	}

	for (int i = 0; i < M; i++) {
		int U = Edges[i].U;
		int V = Edges[i].V;
		LL W = Edges[i].W;

		if ((Dist[U] < INF) && (Dist[U] + W - Money[V] < Dist[V])) {
			Dist[V] = Dist[U] + W - Money[V];
			Q.push(U);
			Visited[U] = true;
		}
	}
}

void settings() {
	bellmanFord();
}

bool checkCycle() {
	while (!Q.empty()) {
		int Now = Q.front();
		Q.pop();

		for (int i = 0; i < M; i++) {
			int U = Edges[i].U;
			if (U != Now) continue;
			int Next = Edges[i].V;
			if (Visited[Next]) continue;
			Visited[Next] = true;
			Q.push(Next);
		}
	};

	if (Visited[E]) return true;
	return false;
}

void printAnswer() {
	if (Dist[E] == INF) {
		cout << "gg\n";
	}
	else {
		if (checkCycle()) {
			cout << "Gee\n";
		}
		else {
			cout << -Dist[E] << "\n";
		}
	}
}

int main() {
    FASTIO

	init();
	input();
	settings();
	printAnswer();

    return 0;
}