[알고리즘][Python] 백준 11779 최소 비용 구하기 2 문제 풀이

문제 출처 : www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

---

문제 해석 : 출발점에서 목적지까지 가는 경로와 비용이 주어 졌을때 최소 비용과 거치는 정점수, 정점을 출력하는 문제이다.

 

문제 풀이 : 다익스트라 알고리즘을 통해서 최소비용을 구하고, 중간에 경로를 기록하면 된다.

---

풀이 코드

def dijkstra(s):
    distance = [INF] * (N+1)
    distance_path = [[] for _ in range(N+1)]
    q = [[0, s, [s]]]
    distance[s] = 0

    while q:

        now_cost, now_vertex, path = heapq.heappop(q)

        for next_cost, next_vertex in Q[now_vertex]:
            if next_cost + now_cost < distance[next_vertex]:
                next_cost += now_cost
                distance[next_vertex] = next_cost
                distance_path[next_vertex] = path + [next_vertex]
                heapq.heappush(q, [next_cost, next_vertex, path + [next_vertex]])

    return distance, distance_path

import sys, heapq
INF = sys.maxsize

N = int(input())
M = int(input())
Q = [[] for _ in range(N+1)]

for _ in range(M):
    start, end, cost = map(int, input().split())

    Q[start].append([cost, end])

S, E = map(int, input().split())
answer, answer_path = dijkstra(S)

print(answer[E])
print(len(answer_path[E]))
for element in answer_path[E]:
    print(element, end = " ")

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.