056 최단경로

첫번째 코드

 

그래프와 가중치를 주면서

더한 값이 현재 값보다 작은 경우 갱신하는 다익스트라를 이용하는 문제이다.

 

뭔가 이해가 안되는 듯 이해가 될 것 같기도 한 느낌이다....

코드는 책을 참고했다!

 

import sys
input = sys.stdin.readline
from queue import PriorityQueue

V,e = map(int, input().split())
k = int(input())
distance = [sys.maxsize] * (V+1)
visited = [False] * (V+1)
A = [[] for _ in range(V+1)]
queue = PriorityQueue()

for _ in range(e):
    u, v, w = map(int, input().split())
    A[u].append((v, w))

queue.put((0, k))
distance[k] = 0

while queue.qsize() > 0:
    now = queue.get()
    c_v = now[1]
    if visited[c_v]:
        continue
    visited[c_v] = True
    for temp in A[c_v]:
        next = temp[0]
        weight = temp[1]
        if distance[next] > distance[c_v] + weight:
            distance[next] = distance[c_v] + weight
            queue.put((distance[next], next))

for i in range(1, V+1):
    if visited[i]:
        print(distance[i])
    else:
        print("INF")

 

통과!

첫번쨰 푸는거니까 속상해하지 말고 다음에도 풀어보자!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1753.%E2%80%85%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C

programmers/백준/Gold/1753. 최단경로 at main · ornni/programmers