https://school.programmers.co.kr/learn/courses/30/lessons/72413
i
까지 같이간다고 가정하고 식을 작성했을 때, answer를 계속 최솟값으로 업데이트 시켜주면 된다. (여기가 핵심!! 굳이 A와 B가 어디까지 같이 가고 어디서부터 헤어지는 지 안 구해줘도 됨)from collections import defaultdict
from heapq import heappush, heappop
def solution(n, s, a, b, fares):
graph = defaultdict(list)
answer = int(1e9)
#parent 배열 완성, 유효한 그래프 완성
for src, dest, fee in fares:
graph[src].append((dest, fee))
graph[dest].append((src, fee))
#다익스트라
def dijkstra(start):
distance = [int(1e9) for _ in range(n+1)]
q = []
heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heappop(q)
if distance[now] < dist:
continue
for v, fee in graph[now]:
cost = dist + fee
if cost < distance[v]:
distance[v] = cost
heappush(q, (cost, v))
return distance
distance_list = [[]] + [dijkstra(i) for i in range(1, n+1)]
for i in range(1, n+1):
answer = min(answer, distance_list[s][i] + distance_list[i][a] + distance_list[i][b])
return answer