문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72413

문제 설명

• 두 사람이 택시비를 아끼기 위해 특정 지점까지 택시를 함께 탈 수 있다

• 택시비의 합의 최솟값 리턴

풀이

• (경유지까지의 최단 거리) + (경유지 to A 의 최단 거리) + (경유지 to B 의 최단 거리) 의 최솟값을 구한다

• V가 200 이기 때문에 가능한 경유지는 완전 탐색

코드

import heapq


gn = 0
adj_list = []


def solution(n, start, a, b, fares):
    global gn, adj_list
    answer, gn, adj_list = init(n, fares)
    for mid in range(1, n+1):
        dist1 = min_dist(start, mid)
        dist2 = min_dist(mid, a)
        dist3 = min_dist(mid, b)
        answer = min(answer, dist1 + dist2 + dist3)
    return answer


def init(n, fares):
    adj_list = [[] for _ in range(n+1)]
    for a, b, c in fares:
        adj_list[a].append((b, c))
        adj_list[b].append((a, c))
    return float('inf'), n, adj_list


def min_dist(start, end):
    distance = [float('inf')] * (gn + 1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        tmp_dist, now = heapq.heappop(q)
        if distance[now] < tmp_dist:
            continue
        for after, cost in adj_list[now]:
            tmp_dist = distance[now] + cost
            if distance[after] > tmp_dist:
                distance[after] = tmp_dist
                heapq.heappush(q, (tmp_dist, after))
    return distance[end]