문제

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

풀이

아이디어

• 다익스트라 알고리즘: 어떤 한 정점으로부터 모든 정점까지로의 최단거리를 구한다.
• 따라서, 1번부터 N번까지 다익스트라를 돌린 distance 배열들을 쫙 이어붙여서 2차원 배열을 만들면, 모든 정점에서 모든 정점으로의 최소거리(최소 요금)을 알 수 있다.
  - A와 B가 같이 가는 구간이 없더라도, 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