합승 택시 요금

from math import inf def solution(n, s, a, b, fares): # 3 <= n <= 200로 비교적 작습니다. # Floyd-Warshall로 모든 정점 간 최단 거리를 구한 뒤에 생각해봅시다. s -= 1; a -= 1; b -= 1 weights = dict() for u, v, w in fares: weights[(u-1, v-1)] = w weights[(v-1, u-1)] = w dist = [[inf] * n for _ in range(n)] for u in range(n): for v in range(n): if u == v: dist[u][v] = 0 elif (u, v) in weights: dist[u][v] = weights[(u, v)] for k in range(n): for u in range(n): for v in range(n): dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]) # s~k, k~a, k~b의 합이 가장 작을 때의 합을 구합니다. mn = min(dist[s][k] + dist[k][a] + dist[k][b] for k in range(n)) return mn