합승 택시 요금 - 프로그래머스

합승 택시 요금 - 프로그래머스

• A와 B가 출발지에서 각자 목적지에 가는 것과
• 특정 지점까지 같이 간 이후에, 각자 목적지에 가는 것을 비교하여 최소값을 도출

import heapq

def di(adj, num, s, e):
    heap = []
    heapq.heappush(heap, [0, s])
    dist = [float('inf')] * (num + 1)
    dist[s] = 0

    while heap:
        cost, node = heapq.heappop(heap)
        if dist[node] < cost:
            continue
        for i, j in adj[node]:
            j += cost
            if j < dist[i]:
                dist[i] = j
                heapq.heappush(heap, [j, i])
    return dist[e]

def solution(n, s, a, b, fares):
    adj = [[] for _ in range(n + 1)]
    for x, y, c in fares:
        adj[x].append([y, c])
        adj[y].append([x, c])
    ret = di(adj, n, s, a) + di(adj, n, s, b)
    for i in range(1, n + 1):
        if s != i:
            ret = min(ret, di(adj, n, s, i) + di(adj, n, i, a) + di(adj, n, i, b))
    return ret