사용자 도구

사이트 도구


ps:problems:boj:6002

Job Hunt

ps
링크acmicpc.net/…
출처BOJ
문제 번호6002
문제명Job Hunt
레벨골드 3
분류

SPFA

시간복잡도O(V(P+F))
인풋사이즈V<=220, P<=150, F<=350
사용한 언어Python
제출기록35088KB / 164ms
최고기록84ms
해결날짜2021/09/23

풀이

  • 음수 가중치가 있는 그래프에서의 최단 경로를 구하는 기본적인 문제. 최대 이익을 구하는 문제이지만, 버는 돈을 -로 쓰는 돈을 +로 바꿔서 그래프를 만들고 최소 코스트를 구한뒤 그 결과값에 다시 -를 붙여주면 끝.
  • 단일 출발지 최단 경로 (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()

토론

댓글을 입력하세요:
Z​ K H A M
 
ps/problems/boj/6002.txt · 마지막으로 수정됨: 2021/09/23 14:42 저자 teferi