[백준 11779번] 최소비용 구하기 2 (Python)

해당 문제를 풀기 위해 다익스트라 개념에 대해 먼저 알고 있어야한다.

2024.03.28 - [CS/Algorithm] - [알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python)

 

또한 해당 문제의 1단계인 최소비용 구하기를 풀고 풀면 좋을 것 같다.

이전 문제 풀이 : [백준 1916번] 최소비용 구하기

 

문제 링크

[백준 11779번] 최소비용 구하기 2

 

문제 요약

N개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착에 도착하는 M개의 버스가 있다.

A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용과 경로 출력하기

(도시의 개수 1 <= N <= 1000, 버스의 개수는 1 <= M <= 100,000)

 

접근 방법 정리

- 한 도시에서 출발해 다른 도시에 도착 -> 단방향 그래프

- 입력 순서대로 받고 (첫 줄 도시의 개수, 두번째 줄 버스의 출발 도시, 세번째 줄 ~ M+2줄 까지 버스의 정보, 마지막줄 출발 도시번호, 도착 도시번호)

- dijkstra를 이용해 최단거리를 구한다.

    - INF로 도시의 개수만큼 거리를 초기화

    - 버스의 정보를 graph로 만들어 저장

    - 다익스트라에 힙을 사용해 구현한다.

- 경로를 저장하기 위해 line을 선언하고 거리가 더 짧은 경우 거리 값이 바뀔 때 line값도 변경되도록 적용

 

코드

import heapq

n = int(input())
m = int(input())
INF = 1e9

arr = [[] for _ in range(n + 1)]
line = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for i in range(m):
    a, b, c = map(int, input().split())
    arr[a].append((b, c))

s, g = map(int, input().split())

def dijkstra(s):
    heap = []
    heapq.heappush(heap, (s, 0))
    distance[s] = 0
    line[s].append(s)

    while heap:
        start, cost = heapq.heappop(heap)

        if distance[start] < cost:
            continue

        for z in arr[start]:
            a, b = z
            c = cost + b

            if distance[a] > c:
                distance[a] = c
                line[a] = line[start] + [a]
                heapq.heappush(heap, (a, c))

dijkstra(s)

print(distance[g])
print(len(line[g]))
print(*line[g])