내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
Job Hunt
ps:problems:boj:6002
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Job Hunt ====== ===== 풀이 ===== * 음수 가중치가 있는 그래프에서의 최단 경로를 구하는 기본적인 문제. 최대 이익을 구하는 문제이지만, 버는 돈을 -로 쓰는 돈을 +로 바꿔서 그래프를 만들고 최소 코스트를 구한뒤 그 결과값에 다시 -를 붙여주면 끝. * [[ps:단일 출발지 최단 경로]] 에서 설명한대로 SPFA를 사용해서 O(VE)에 구할 수 있다. * 이동하면서 번 금액 뿐 아니라, 출발점에서도 D를 벌고 시작한다는 점에 유의하자. SPFA에서 얻는 결과에 D를 더해서 출력해야 한다. ===== 코드 ===== <dkpr py> """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() </dkpr> * Dependency: [[:ps:teflib:tgraph#spfa|teflib.tgraph.spfa]] {{tag>BOJ ps:problems:boj:골드_3}}
ps/problems/boj/6002.txt
· 마지막으로 수정됨: 2021/09/23 14:42 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로