사용자 도구

사이트 도구


ps:problems:boj:11657

타임머신

ps
링크acmicpc.net/…
출처BOJ
문제 번호11657
문제명타임머신
레벨골드 4
분류

SPFA

시간복잡도O(VE)
인풋사이즈V<=500, E<=6000
사용한 언어Python
제출기록35100KB / 408ms
최고기록344ms
해결날짜2021/09/10

풀이

  • 그래프에서 최단 경로를 찾는 기본적인 문제. 걸리는 시간이 음수일수도 있으므로, 벨만포드 알고리즘이나 SPFA를 사용해야한다. 단일 출발지 최단 경로 (Single Source Shortest Path)에서 언급한대로 SPFA를 사용해서 풀었다.
  • SPFA의 시간복잡도는 O(VE).

코드

""""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()

토론

댓글을 입력하세요:
S O Z K K
 
ps/problems/boj/11657.txt · 마지막으로 수정됨: 2021/09/23 14:41 저자 teferi