Job Hunt

• 음수 가중치가 있는 그래프에서의 최단 경로를 구하는 기본적인 문제. 최대 이익을 구하는 문제이지만, 버는 돈을 -로 쓰는 돈을 +로 바꿔서 그래프를 만들고 최소 코스트를 구한뒤 그 결과값에 다시 -를 붙여주면 끝.
• 단일 출발지 최단 경로 (Single Source Shortest Path) 에서 설명한대로 SPFA를 사용해서 O(VE)에 구할 수 있다.
• 이동하면서 번 금액 뿐 아니라, 출발점에서도 D를 벌고 시작한다는 점에 유의하자. SPFA에서 얻는 결과에 D를 더해서 출력해야 한다.

"""Solution code for "BOJ 6002. Job Hunt".

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

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')


def main():
    D, P, C, F, S = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(C)]
    for _ in range(P):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        wgraph[A - 1][B - 1] = -D
    for _ in range(F):
        J, K, T = [int(x) for x in sys.stdin.readline().split()]
        wgraph[J - 1][K - 1] = T - D

    answer = D - min(tgraph.spfa(wgraph, S - 1))
    print('-1' if answer == INF else answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa