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