클라우드로 크고 싶은 블로그 입니다

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

파이썬으로 알고리즘 정리하기 위해 아래와 같이 작성했다.

import sys
import heapq

def dijkstra(graph, start):
    n = len(graph)

    # 최초 거리를 무한으로 설정
    dist = [float('inf')] * n

    # 시작점의 거리는 0
    dist[start] = 0
    # 시작점을 큐에 추가
    heap = [(0, start)]
    while heap:
        # u : 지금 방문한 노드
        # d : 시작점에서 u 까지의 거리
        # v : u 에서 연결 된 노드 (다음에 방문할 노드)
        # w : u -> v 까지의 거리
        # dist[u] : 지금까지 계산한 u 까지의 최소 거리
        # dist[v] : 지금까지 계산한 v 까지의 최소 거리
        
        # 방문할 노드 꺼냄
        (d, u) = heapq.heappop(heap)

        # 이전에 더 가깝게 방문했다면 패스
        if d > dist[u]:
            continue

        # 연결된 노드 들을 확인
        for w, v in graph[u]:
            # 방문한 노드까지의 거리 + 다음 노드 까지의 거리가 이전에 계산한 값보다 짧으면,
            # 거리값을 저장 후 우선순위 큐에 저장
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

input=sys.stdin.readline
V, E = map(int, input().split())
# 정점(노드)의 번호가 1번 부터 시작 해서 1 뺌
K = int(input()) - 1

graph = [[] for _ in range(V)]

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u-1].append((w, v-1))

dist = dijkstra(graph, K)

for i in range(V):
    if dist[i] == float('inf'):
        print("INF")
    else:
        print(dist[i])


'''
예제 입력
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력
0
2
3
7
INF
'''