오민식의 고민

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	10997	2142	1250	16.718%

문제

오민식은 세일즈맨이다.

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

오민식은 고민에 빠졌다. 어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 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

출처

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: djm03178
• 데이터를 추가한 사람: gkgg123, sait2000
• 문제의 오타를 찾은 사람: jh05013, typhoon

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 벨만–포드

---

주의 사항

순환이 도착 지점에 영향을 줄 수 있도록 많은 시도가 필요하다.

통과된 코드

#include <iostream>
#include <vector>

using namespace std;

constexpr int MAXN = 50;

constexpr long long int INF = -INT64_MAX;

long long int disArr[MAXN];

int N, S, D, M, V, U, W, G[MAXN];

bool check = false;

vector<pair<int, int>> graph[MAXN];

int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    std::cout.tie(NULL);

    cin >> N >> S >> D >> M;

    // 교통 수단을 입력받는다.
    for (int i = 0; i < M; i++) {
        cin >> V >> U >> W;
        // 단방향 교통수단 출발, 도착, 비용
        graph[V].push_back(make_pair(U, -W));
    }

    // 도시에서 버는 비용입력
    for (int i = 0; i < N; i++) cin >> G[i];

    fill(disArr, disArr + MAXN, INF);

    disArr[S] = G[S];

    // N번 이후부터는 순환 체크
    // 순환이 있는지 충분히 확인
    for (int k = 1; k <= N * 2; k++) { 
        for (int i = 0; i < N; i++) { // 시작 정점
            for (int j = 0; j < graph[i].size(); j++) {
                int v = graph[i][j].first; // 도착점
                int weight = graph[i][j].second; // 가중치

                if (disArr[i] == -INF) disArr[v] = -INF; // 출발지가 순환이라면 도착지도 순환
                else if (disArr[i] != INF && disArr[i] + weight + G[v] > disArr[v]) {
                    disArr[v] = disArr[i] + weight + G[v]; // 업데이트

                    if (k >= N) disArr[v] = -INF; // 순환찾기
                }
            }
        }
    }

    if (disArr[D] == -INF) cout << "Gee"; // 순환에 포함
    else if (disArr[D] == INF) cout << "gg"; // 도착 불가능 
    else cout << disArr[D];

    return 0;

}

추가 반례

예제 입력 A

5 0 4 6
0 1 10000
1 2 0
2 1 0
1 3 0
0 3 0
3 4 0
0 0 1 0 0

예제 출력 A

Gee

예제 입력 B

5 0 0 0
1 2 3 4 5

예제 출력 B

1

예제 입력 C

50 0 49 50
0 1 0
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
39 40 0
40 41 0
41 42 0
42 43 0
43 44 0
44 45 0
45 46 0
46 47 0
47 48 0
48 49 0
49 0 0
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000

예제 출력 C

Gee

예제 입력 D

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

예제 출력 D

2

예제 입력 E

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

예제 출력 E

5

예제 입력 F

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

예제 출력 F

Gee