15422. Bumped! (Python)

 

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

15422번: Bumped!

 

풀이

 어떤 한 지점에서 시작해서 최단 거리를 구하는 문제로 다익스트라를 활용해서 문제를 해결할 수 있다. 이 문제에서 비교해야 할 것은 다음과 같다.

s: 여행을 시작하는 도시
t: 여행 목적지(도시)
u: 비행 시작 도시
v: 비행 도착 도시

dijkstra(a, b) : a에서 b까지의 최소 비용

1. s에서 t까지 길을 통해서만 가는 경우 발생하는 최소 비용(비행 편 사용하지 않음)

    -> dijkstra(s, t)

2. s에서 u까지 길을 통해서 가는 최소 비용 + u에서 v까지 무료 비행 편 이용(0원) + v에서 t까지 길을 통해서 가는 최소 비용

    -> dijkstra(s, u) + dijkstra(v, t)

 

 처음 변수에 1번에서 구한 값을 넣어준 후 각 비행편마다 2번을 구해서 둘 중 최솟값을 구해서 최소 비용을 갱신해주면 된다.

 

코드

<Python>

import heapq
import math
 
INF = math.inf
 
 
def dijkstra(start, end):
    dist = [INF] * n
 
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
 
    while q:
        cost, now = heapq.heappop(q)
 
        if dist[now] < cost:
            continue
        
        for (nextNode, cents) in graph[now]:
            nextCost = cost + cents
 
            if nextCost < dist[nextNode]:
                dist[nextNode] = nextCost
                heapq.heappush(q, (nextCost, nextNode))
    
    return dist[end]
 
 
if __name__ == '__main__':
    # n: city의 개수
    # m: road의 개수
    # f: flight의 개수
    # s: 여행을 시작하는 city 번호
    # t: 여행 가려는 city 번호
    n, m, f, s, t = map(int, input().split())
    graph = [[] for _ in range(n)]
 
    for _ in range(m):
        # a에서 b로, b에서 a로 나는 비용 c
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
 
    # s에서 t로 가는데 비행 편을 사용하지 않고 갔을 때의 최소 비용
    ans = dijkstra(s, t)
 
    for _ in range(f):
        # u에서 v로 가는 비행 편
        u, v = map(int, input().split())
 
        # ans와 s -> u로 길을 통해서 간 후 u에서 v로 비행 편을 사용한 후 v에서 t로 길을 통해서 갔을 때의 비용 비교 
        ans = min(ans, dijkstra(s, u) + dijkstra(v, t))
    
    print(ans)