사용자 도구

사이트 도구


ps:problems:boj:1753

최단경로

ps
링크acmicpc.net/…
출처BOJ
문제 번호1753
문제명최단경로
레벨골드 5
분류

그래프, 최단경로

시간복잡도O(ElogV)
인풋사이즈V<=20,000, E<=300,000
사용한 언어Python
제출기록60344KB / 744ms
최고기록532ms
해결날짜2021/01/28

풀이

  • 양수 가중치를 갖는 방향그래프에서의 최단경로. 따라서, 다익스트라 알고리즘을 쓰면 끝나는 문제이다.
  • 문제에서 친절하게 강조했지만, 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의하자. 가장 짧은 간선만 남기면 된다.
  • 다익스트라 알고리즘만 돌리면 되니까 시간복잡도는 O(ElogV)

코드

"""Solution code for "BOJ 1753. 최단경로".

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

Tags: [Dijkstra]
"""

import sys
from teflib import graph as tgraph

INF = float('inf')


def main():
    V, E = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(V)]
    K = int(sys.stdin.readline())
    for _ in range(E):
        u, v, w = [int(x) for x in sys.stdin.readline().split()]
        if w < (e := wgraph[u - 1]).get(v - 1, INF):
            e[v - 1] = w

    dists = tgraph.dijkstra(wgraph, K - 1)
    print(*('INF' if dist == INF else dist for dist in dists), sep='\n')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
G R N B V
 
ps/problems/boj/1753.txt · 마지막으로 수정됨: 2022/09/16 17:30 저자 teferi