백준 #1753. 최단경로: 다익스트라/골드4

문제 링크 :

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

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

문제 유형 : 다익스트라

• 단방향 그래프에서의 최단 거리 구하는 문제
• cost가 자연수

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. 입력 변수
2. 다익스트라 함수 정의하기
3. 시작점으로 부터 N 개의 정점까지 최단 거리 출력
   • INF 인 경우, string “INF” 출력

🚩제출한 코드

import sys
import heapq
input = sys.stdin.readline
INF = 1e12
V , E = map(int, input().split())
start = int(input())

graph = [[] for _ in range(V+1)]
for _ in range(E) : 
    a,b , c =map(int, input().split())
    graph[a].append((b,c))

distance = [INF]*(V+1)
# 다익스트라 함수 
def dijkstra(start) :
    q = []
    distance[start]=0 
    heapq.heappush(q,(0,start))
    while q : 
        # 2.경유지 뽑기 
        dist , now = heapq.heappop(q)
        # 3-1. 이미 처리한 경유지인 경우 -> 무시
        if distance[now] < dist : 
            continue
        #3-2. 현재 경유지에서 바로 갈 수 있는 노드 처리
        for t in graph[now]:
            cost = dist + t[1] # 경유지를 거친 start - t[0] 의 거리
            if cost < distance[t[0]] :  # 경유지 cost 가 더 작으면 업데이트 
                distance[t[0]] = cost 
                heapq.heappush(q, (cost , t[0]))
#4. 출력
dijkstra(start)
for node in range(1 , V+1) : 
    print("INF"if distance[node] >= INF else distance[node]  )