[programmers] 합승 택시 요금 (python)

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

프로그래머스

---

문제 회고

다익스트라 알고리즘이 익숙지 않아서 개념 공부를 하고 푼 문제

다익스트라 알고리즘을 공부하고도 바로 풀지는 못했다. 문제를 작은 문제로 나눠서 풀었다. S와의 최단거리, A와의 최단 거리, B와의 최단 거리를 가지는 한 point를 찾아서 그때의 비용을 답으로 구한다. 총 세 가지 다익스트라 distance를 구했다. (S, A, B)

---

import heapq

def solution(n, s, a, b, fares):
    answer = 0
    INF = int(1e9)
    graph = [[] for _ in range(n + 1)]
    for point_a, point_b, fare in fares:
        graph[point_b].append((point_a, fare))
        graph[point_a].append((point_b, fare))
        
    def dijkstra(start):
        distance = [INF] * (n + 1)
        q = []
        heapq.heappush(q, (0, start))
        distance[start] = 0
        
        while q:
            dist, now = heapq.heappop(q)
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
        return distance
    
    a_distance = dijkstra(a)
    b_distance = dijkstra(b)
    s_distance = dijkstra(s)
    min_distance = INF
    for i in range(len(a_distance)):
        if a_distance != INF and b_distance != INF and s_distance != INF:
            min_distance = min(min_distance, a_distance[i] + b_distance[i] + s_distance[i])
    return min_distance