[Python] 백준 1916 최소비용 구하기 | 다익스트라 | 시간초과

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1916번: 최소비용 구하기

 

 

문제 해결 포인트

- 받을 입력이 많으므로 sys.stdin.realine 을 사용한다. (시간 초과 해결)

- 전형적인 다익스트라 문제 유형이다

- 우선순위 큐(최소힙)를 사용하여 최소 거리 노드를 선택

- distance : start 노드로부터 각 노드의 거리를 저장 (INF 로 초기화)

- graph : 각 노드의 연결 리스트

 

 

다익스트라 정리 글 참고

2023.05.17 - [🧪Computer Science/알고리즘] - [알고리즘] 최단 경로 알고리즘 | 다익스트라 | 플로이드 워셜

 

작성 코드

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
distance = [INF]*(N+1)

for _ in range(M):
    v1, v2, w = map(int, input().split())
    graph[v1].append((v2, w))

def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

A, B = map(int, input().split())
dijkstra(A)
print(distance[B])

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚