Python/백준] 5972 택배 배송

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

5972번: 택배 배송

<문제 해설>

데이크스트라 문제이다.

bfs랑 비슷하게 풀면되는데 어떤 노드에 도착할때 방문하는데 사용한 비용이 더 낮다면 그노드부터는 한번더 탐색하는 방식이다.

1. 1번 노드에서 출발한다 1번노드 방문하는데는 0의 비용이든다.
2. 1번에서 2,4번으로 이동한다. 2노드로 가는데에는 1의 비용이 들고 4의 노드로 가는데에는 4의 비용이든다.
3. 2번,4번노드에서 이동한다. 2에서 1로 가려는데 1로 가는 최소 비용이 0이라 2보다 큼으로 못간다. 4번노드로는 1 +
    0으로 아까 기록된 4보다 작아서 4번 노드로 갈수 있다. 4번 노드에서는 4번까지 도착비용이 1인 노드로 초기화 되어서 다시 탐색하게 된다.
4. 모든 탐색이 끝났다면 마지막 노드의 visited엔 최소 비용이 기록 되었을 것임으로 그걸 출력해준다.

<코드>

import sys
from collections import deque

def search():
    while(que):
        x = que.popleft()
        for g in G[x]:
            if visited[g[0]] > visited[x] + g[1]:
                visited[g[0]] = visited[x] + g[1]
                que.append(g[0])

N, M = map(int, sys.stdin.readline().split())

visited = [float('inf')] * (N + 1)
G = [[] for _ in range(N + 1)]

visited[1] = 0
for m in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    G[A].append([B,C])
    G[B].append([A,C])
que = deque([1])
search()

print(visited[N])