내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
타임머신
ps:problems:boj:11657
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 타임머신 ====== ===== 풀이 ===== * 그래프에서 최단 경로를 찾는 기본적인 문제. 걸리는 시간이 음수일수도 있으므로, 벨만포드 알고리즘이나 SPFA를 사용해야한다. [[ps:단일 출발지 최단 경로]]에서 언급한대로 [[ps:단일 출발지 최단 경로#shortest_path_faster_algorithm_spfa|SPFA]]를 사용해서 풀었다. * SPFA의 시간복잡도는 O(VE). ===== 코드 ===== <dkpr py> """"Solution code for "BOJ 11657. 타임머신". - Problem link: https://www.acmicpc.net/problem/11657 - Solution link: http://www.teferi.net/ps/problems/boj/11657 Tags: [SPFA] """ import sys from teflib import tgraph INF = float('inf') START = 0 def main(): N, M = [int(x) for x in sys.stdin.readline().split()] wgraph = [{} for _ in range(N)] for _ in range(M): A, B, C = [int(x) for x in sys.stdin.readline().split()] try: min_edge_cost = wgraph[A - 1][B - 1] wgraph[A - 1][B - 1] = min(min_edge_cost, C) except KeyError: wgraph[A - 1][B - 1] = C dist = tgraph.spfa(wgraph, START) if -INF in dist: print(-1) else: for dist_to_i in dist[1:]: print('-1' if dist_to_i == INF else dist_to_i) if __name__ == '__main__': main() </dkpr> * Dependency: [[:ps:teflib:tgraph#spfa|teflib.tgraph.spfa]] {{tag>BOJ ps:problems:boj:골드_4}}
ps/problems/boj/11657.txt
· 마지막으로 수정됨: 2021/09/23 14:41 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로