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

---

1. 전체 코드

def solution(n, s, a, b, fares):
    INF = float('inf')
    # 인접 행렬
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    for u, v, w in fares:
        graph[u][v] = w
        graph[v][u] = w
    for k in range(1, n + 1):
        graph[k][k] = 0
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    min_val = float('inf')
    for i in range(1, n + 1):
        tot = graph[i][s] + graph[i][a] + graph[i][b]
        print(tot)
        min_val = min(tot, min_val)
    return min_val


print(solution(7, 3, 4, 1, [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]]))

2. 후기

4→1→5 : A, B가 합승하여 택시를 이용합니다. 예상 택시요금은 10 + 24 = 34원 입니다.
...
지점갯수 n은 3 이상 200 이하인 자연수입니다.

이 부분을 읽었다면 플로이드 워셜 알고리즘이 떠올랐어야 한다. 다익스트라 알고리즘으로도 풀 수 있다.