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

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

from collections import defaultdict
from heapq import heappush, heappop

def solution(n, s, a, b, fares):
    edge = defaultdict(defaultdict)
    answer = float('inf')
    
    # 각 점들이 연결된 edge를 먼저 구성한다.
    for c, d, w in fares:
        edge[c][d] = w
        edge[d][c] = w
    
    # 공유하는 지점을 완전 탐색을 이용해서, 가장 비용이 적은 지점을 찾는다.
    # 이때 각 지점에서 다른 지점까지의 최소 비용을 찾아야 하므로 다익스트라 알고리즘을 활용한다.
    # 효율성도 필요하므로, 우선순위큐를 이용한다.
    for num in range(1, n + 1):
        dist = defaultdict(lambda : float('inf'))
        dist[num] = 0
        q = [(0, num)]
        
        while q:
            fare, e = heappop(q)
            
            if dist[e] >= fare:

                for e2, f2 in edge[e].items():
                    if dist[e2] > fare + f2:
                        dist[e2] = fare + f2
                        heappush(q, (fare + f2, e2))
                        
        answer = min(answer, dist[s] + dist[a] + dist[b])
    return answer