백준 1916

<최소 비용 구하기>

난이도 : 골드 5

1. 백준 문제
   1916

2. 코드 알고리즘

   1753번과 풀이와 코드가 동일해 설명을 생략
   아래 1753번 풀이를 참조하세요

1753 풀이

3. 코드

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

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

from queue import PriorityQueue

#인접리스트 작성
A =[[] for _ in range(n+1)]
for i in range(m):
    u, v, w = map(int, input().split())
    A[u].append((v, w))

#출발노드, 도착노드 입력
start, end = map(int, input().split())

#distance 초기화
max = sys.maxsize
D = [max]*(n+1)
D[start] = 0

#방문 리스트
visited = [False]*(n+1)

#우선 순위 큐
q = PriorityQueue()
q.put((0, start)) #거리로 정렬되도록 먼저 작성하기
while q.qsize()>0:
    now = q.get() #거리리스트 값이 가장 작은 노트 선택(이미 우선정렬된 큐)
    now_s = now[1] #출발 노드
    if not visited[now_s]: #방문 안한 경우에만
        visited[now_s] = True
        for v,w in A[now_s]: 
            if D[v] > D[now_s] + w and not visited[v]:
                D[v] = D[now_s] + w
                q.put((D[v], v)) #거리값이 우선 오도록

#최종 결과 출력
print(D[end])