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

---

문제 분석

벨만-포드 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 하는 문제이다. 기존 벨만-포드는 최단 거리를 구하는 알고리즘이지만, 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 하고 싶기 때문에 업데이트 방식을 반대로 변경해야한다. 또한 돈을 무한히 많이 버는 케이스가 있다고 하는 것을 바탕으로 음수 사이클이 아닌 양수 사이클을 찾도록 변경이 필요하다.
마지막으로 예외처리가 1개 필요한데, 양수 사이클이 있어도 출발 노드에서 이 양수 사이클을 이용해 도착 도시에 가지 못하는 경우이다. 즉, 양수 사이클에 도착노드가 없는 경우이다.
이 부분을 해결하기 위해 에지의 업데이트를 N-1번이 아닌, 충분히 큰 수만큼 추가로 돌리면서, 업데이트를 수행하도록 하였다.

---

소스 코드

# 오만식의 고민

import sys
input = sys.stdin.readline

N, startCity, endCity, M = map(int, input().split())
arr = []
maxGain = [-sys.maxsize] * (N)

for _ in range(M):
    s, e, w = map(int, input().split())
    arr.append((s,e,w))

benefit = list(map(int, input().split()))

maxGain[startCity] = benefit[startCity]

for i in range(N + 101):
    for s,e,w in arr:
        if maxGain[s] == -1* sys.maxsize:
            continue
        elif maxGain[s] == sys.maxsize:
            maxGain[e] = sys.maxsize
        elif maxGain[s] - w + benefit[e] > maxGain[e]:
            maxGain[e] = maxGain[s] -w + benefit[e]
            if i >= N - 1:
                maxGain[e] = sys.maxsize
          
if maxGain[endCity] == -sys.maxsize:
    print("gg")
elif maxGain[endCity] == sys.maxsize:
    print("Gee")
else:
    print(maxGain[endCity])