[백준/Python] 1219번 오민식의 고민

문제

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

 

소스코드

import sys
input = sys.stdin.readline

n, start, end, m = map(int, input().split())
graph = {}
for i in range(m):
    a, b, c = map(int, input().split())
    if a not in graph:
        graph[a] = []
    graph[a].append((b, c))
money_list = list(map(int, input().split()))

def trans_bellman_ford(start):
    distance_list = [-1e9] * (n + 1)
    distance_list[start] = money_list[start]

    for i in range(n + 100):
        for u in graph:
            for v, w in graph[u]:
                if distance_list[u] == -1e9:
                    continue
                elif distance_list[u] >= 1e9:
                    distance_list[v] = 1e9
                elif distance_list[v] < distance_list[u] + money_list[v] - w:
                    distance_list[v] = distance_list[u] + money_list[v] - w
                    if i >= n - 1:
                        distance_list[v] = 1e9
    return distance_list
data = trans_bellman_ford(start)
if data[end] <=-1e9:
    print("gg")
elif data[end] >= 1e9:
    print("Gee")
else:
    print(data[end])

 

변형된 벨만포드 알고리즘을 사용합니다. 

가중치를 뒤집는 것으로 양수사이클을 찾습니다. 

n - 1 사이클부터 갱신되는 노드는 양수사이클인것으로 간주하여 체크하고 양수 사이클 노드가 충분히 전파될 수 있도록 사이클을 n + 100번 실행합니다. 

 

변형된 벨만포드 알고리즘으로 생성된 도착리스트를 이용하여 도착지의 값이 초기값이라면 접근할 수 없으니 gg를 양수 사이클이라면 돈을 무한으로 벌 수 있으니 Gee를 출력합니다.