테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 오민식의 고민 ======

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


===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:tgraph#spfa|teflib.tgraph.spfa]]

{{tag>BOJ ps:problems:boj:골드_2}}