문제 링크

🔷 분류

그래프 이론, 그래프 탐색, 최단 경로, 벨만–포드

✒️ 문제 설명

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

오민식은 고민에 빠졌다.

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

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

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

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

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

⬅️ 입력

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

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

➡️ 출력

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

💻 코드 (C++)

#include <iostream>
#include <tuple>
#include <vector>
#include <limits.h>
using namespace std;
typedef tuple<int, int, int> edge; // <start, end, weight>

vector<edge> A;
long dist[51];
long earn[51];
int a, b, n, m;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fill(dist, dist+51, LONG_MIN);
	cin >> n >> a >> b >> m;
	for(int i = 0; i < m; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		A.push_back({s, e, w});
	}
	for(int i = 0; i < n; i++) {
		cin >> earn[i];
	}
	
	// Bellman-Ford
	dist[a] = earn[a];
	for(int i = 0; i < n + 50; i++) { // pCycle 확산하도록 
		for(int j = 0; j < m; j++) {
			int start = get<0>(A[j]);
			int end = get<1>(A[j]);
			int cost = get<02>(A[j]);
			if(dist[start] == LONG_MIN) continue; // S 미방문이면 continue
			else if(dist[start] == LONG_MAX) dist[end] = LONG_MAX; // S가 pCycle과 연결이면 E도 연결
			else if(dist[end] < dist[start] + earn[end] - cost) { // 더 많은 돈 벌면
				dist[end] = dist[start] + earn[end] - cost;
				if(i >= n-1) { // pCycle 이면
					dist[end] = LONG_MAX;
				}
			}
		}
	}
	if(dist[b] == LONG_MIN) cout << "gg";
	else if(dist[b] == LONG_MAX) cout << "Gee";
	else cout << dist[b];
	return 0;
}

글 이동

Comments

참고