오민식의 고민

• Job Hunt와 같은 방식으로, 버는 돈을 -로 쓰는 돈을 +로 해서 그래프를 만들면, 음수 가중치가 존재하는 그래프에서의 단일 출발지 최단 경로 (Single Source Shortest Path) 문제가 된다.
• 따라서 SPFA 알고리즘을 돌리고, 얻은 최단경로에 -를 붙여주면 끝. 다만 Job Hunt와 다른 점은, 도착점이 정해져있다는 것이다. 따라서 음수 사이클이 있을때, 음수 사이클이 그래프에 존재하는 것만으로는 충분치 않고, 음수 사이클에서 도착점까지 도달하는 경로가 있을때에만 Gee를 출력해야 한다.
• 시간 복잡도는 O(VE)

"""Solution code for "BOJ 1219. 오민식의 고민".

- Problem link: https://www.acmicpc.net/problem/1219
- Solution link: http://www.teferi.net/ps/problems/boj/1219

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')


def main():
    N, start, dest, M = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(N)]
    for _ in range(M):
        u, v, w = [int(x) for x in sys.stdin.readline().split()]
        try:
            cost = min(wgraph[u][v], w)
        except KeyError:
            cost = w
        wgraph[u][v] = cost
    gain = [int(x) for x in sys.stdin.readline().split()]
    for cost_to in wgraph:
        for v in cost_to:
            cost_to[v] -= gain[v]

    cost = tgraph.spfa(wgraph, start)[dest]
    if cost == INF:
        print('gg')
    elif cost == -INF:
        print('Gee')
    else:
        print(gain[start] - cost)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa