2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import defaultdict
from queue import PriorityQueue

def dijkstra(graph, src):
    ds = {v: float('inf') for v in graph}  # d: src -> v
    ds[src] = 0

    q = PriorityQueue()
    q.put((ds[src], src))  # src부터 탐색 시작

    while not q.empty():
        cur_d, cur_v = q.get()  # cur_d: minimum
        if ds[cur_v] < cur_d:
            continue

        for next_v, d in graph[cur_v].items():  # d: cur_v -> next_v
            new_d = cur_d + d  # next_v를 경유한 거리
            if new_d < ds[next_v]:
                ds[next_v] = new_d
                q.put((new_d, next_v))
    return ds


def solution(n, s, a, b, fares):
    graph = defaultdict(dict)
    for src, dst, w in fares:
        graph[dst][src] = graph[src][dst] = w
    ds = {v: dijkstra(graph, v) for v in sorted(graph)}

    answer = float('inf')
    for c in ds:
        val = ds[s][c] + ds[c][a] + ds[c][b]
#         print(s, c, a, b, f"| {ds[s][c]} + {ds[c][a]} + {ds[c][b]} = {val}")
        answer = min(answer, val)

    return answer