[PS] 오민식의 고민 / C++ (백준 1219번)

오민식의 고민 (백준 1219번)

 

벨만-포드 알고리즘이 기본이 되는 문제지만, 도착 도시까지 가는 길에 사이클이 포함되어 있는지 확인하는 과정을 발상해야 하는 문제.

 

풀이 과정

먼저, 벨만-포드 알고리즘을 적절히 구현하여 나올 수 있는 경우의 수를 모두 구해본다.

1. 도착 불가능: gg 출력
2. 무한 증식 가능: Gee
3. 사이클 없이 도착: 최대 액수 출력
4. 무한 음수값 가능: 무시

1, 3, 4 상황은 벨만-포드 알고리즘과 문제에 대한 이해만 충분하다면 어려움 없이 구현할 수 있다. cost를 최단 경로가 아닌 최대 경로를 구하는 식으로 바꾸기만 하면 된다.

$if(cost[end] < cost[start] - co(경비) + node[end](end에서 벌 수 있는 돈) cost[end] = cost[start] - co + node[end]$

 

"2. 무한 증식 가능"인 상황을 찾기 위해선 n번째 벨만-포드를 돌렸을 때, 이전 값보다 증가한 도시(증가 사이클에 포함된 노드)들에 대해 dfs나 bfs로 도착 지점과 연결되어 있는지 확인해주면 된다.

• 이때, 도착 도시까지 가는 길의 비용이 매우 크던 적던 아무런 상관이 없다.
  (1씩 증가한다 해도, 사이클을 계속 돌리면 무한대이기 때문에 상쇄됨)
• 입력 받을 때, 인접 행렬을 함께 저장해놓으면 간편하게 도착 도시와 연결되어 있는지 확인할 수 있다.
• 추가로, cost를 더하는 과정이 최대 $nm$(2500)번까지 가능하기 때문에 경비의 최댓값인 1,000,000을 2500번 더하면 2,500,000,000로 int 범위를 초과한다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

int n, m, st, en, flag = 0;
ll node[51], cost[51], compare[51];
int vi[51];
int d[51][51];
vector<pair<pair<int, int>, int> > edges;

void bellmanford()
{
	int size = edges.size();
	for (int i = 0; i < size; i++) {
		int start = edges[i].first.first, end = edges[i].first.second;
		ll co = edges[i].second;
		if (cost[start] == 1e10)continue;
		if (cost[end] == 1e10 || cost[end] < cost[start] - co + node[end]) {
			cost[end] = cost[start] - co + node[end];
			vi[end] = 1;
		}
	}
	return;
}

int dfs(int p)
{
	if (p == en) {
		flag = 1;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		if (d[p][i] == 1 && vi[i] == 0) {
			vi[i] = 1;
			dfs(i);
			vi[i] = 0;
		}
	}
	return 0;
}

int main()
{
	scanf("%d %d %d %d", &n, &st, &en, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		edges.push_back(make_pair(make_pair(a, b), c));
		d[a][b] = 1;
	}
	for (int i = 0; i < n; i++)scanf("%lld", &node[i]);

	for (int i = 0; i < n; i++)cost[i] = 10000000000LL;
	cost[st] = node[st];
	vi[st] = 1;
	for (int i = 1; i < n; i++)bellmanford();
	if (vi[en] == 0) {
		printf("gg\n");
		return 0;
	}
	for (int i = 0; i < n; i++) {
		compare[i] = cost[i]; 
		vi[i] = 0;
	}
	bellmanford();
	if (cost[en] > compare[en]) {
		printf("Gee\n");
		return 0;
	}
	for (int i = 0; i < n; i++) {
		if (cost[i] > compare[i]) {
			flag = 0;
			vi[i] = 1;
			dfs(i);
			vi[i] = 0;
			if (flag) {
				printf("Gee\n");
				return 0;
			}
		}
	}
	printf("%lld\n", cost[en]);
	return 0;
}