[Python][백준 5972] 택배 배송

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

5972번: 택배 배송

---

/*
신경써야 할 부분은 바로 :
1. 양방향 가중치
2. 1개 이상의 경로 존재
3. 다익스트라로 접근
*/

---

import heapq

def dijkstra(start):
    
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  

    priority_queue = [(0, start)] 

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

N,M = map(int, input().split())
graph = { i+1 : {} for i in range(N) }

for i in range(M) :
    a,b,c = map(int, input().split())
    if b in graph[a]:
        graph[a][b] = min(c,graph[a][b])
    else :
        graph[a][b] = c
    if a in graph[b]:
        graph[b][a] = min(c,graph[b][a])
    else :
        graph[b][a] = c

start_node = 1
shortest_distances = dijkstra( start_node)
print(shortest_distances[N])

---

풀 때 어려웠던 점 또는 느낀점 :

정신없는 와중에 푸느라 지문을 제대로 못 읽어서 좀 헤맸다

다익스트라의 기본이 되는 문제이며,

이제 난이도 올려가며 비슷한 문제들을 풀어볼 생각이다

 

---

참고할만한 다른 사람 코드 :

import sys
import heapq

n, m = map(int, sys.stdin.readline().rstrip().split())
INF = sys.maxsize
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])

print(nodes)

def Dijkstra(start):
    distances = [INF for _ in range(n+1)]
    distances[start] = 0
    pq = []
    heapq.heappush(pq, [0, start])

    while pq:
        
        cur_cost, cur_node = heapq.heappop(pq)

        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[next_node] > next_cost + cur_cost:
                distances[next_node] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_node])

    return distances

distances = Dijkstra(1)
print(distances)

 

입력값들을 리스트에 저장한 코드이다.

이게 좀 더 깔끔한거 같다 이렇게 짜야겠다.