BOJ - 1916

백준 문제 링크
최소비용 구하기

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 모든 버스의 정보에 대해
   graph[출발도시].append((도착 도시, 버스 비용)) 해준다.
3. 다익스트라 함수 내에서
   distance = [INF] * (n + 1)로 지정한다.
   기본 다익스트라 소스 코드를 전개 후
   마지막엔 distance를 반환한다.
4. 위 과정을 끝내면 dijkstra(start) = [1000000000, 0, 2, 3, 1, 4]로 나오게 되는데, 여기서 dijkstra(start)[end]를 출력하면 끝!

👌🏻코드

import heapq

INF = int(1e9)

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

graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
start, end = map(int, input().split())

def dijkstra(start):
    
    distance = [INF] * (n + 1)
    
    q = []
    
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
            
        for i in graph[now]:
            
            cost = dist + i[1]
            
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
    return distance
                
print(dijkstra(start)[end])