Piggy Back [10652 백준]

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

 

 

3회 다익스트라 알고리즘 시행을 해서 최소비용으로 목적지에 도착하는 경로를 탐색하면 된다. 

import heapq
import sys
from collections import defaultdict

# 다익스트라 알고리즘
def dijkstra(start, graph, n, energy):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        if current_dist > dist[u]:
            continue
        
        for v, weight in graph[u]:
            if dist[v] > current_dist + weight * energy:
                dist[v] = current_dist + weight * energy
                heapq.heappush(pq, (dist[v], v))
    
    return dist

# 입력 처리
B, E, P, N, M = map(int, input().split())
graph = defaultdict(list)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append((v, 1))  # 양방향 그래프
    graph[v].append((u, 1))

# 다익스트라로 각각의 출발점에서 최단 거리 구하기
dist_from_bessie = dijkstra(1, graph, N, B)
dist_from_elsie = dijkstra(2, graph, N, E)
dist_from_barn = dijkstra(N, graph, N, P)

# 최소 에너지를 구하기 위한 계산
min_energy = float('inf')

for i in range(1, N + 1):
    total_energy = dist_from_bessie[i] + dist_from_elsie[i] + dist_from_barn[i]
    min_energy = min(min_energy, total_energy)

# 결과 출력
print(min_energy)