합승 택시 요금 ( Level 3, Python, 2021 Kakao Blind Recruitment )

def solution(n, s, a, b, fares):
    INF = int(1e9)
    graph = [[0 if i == j else INF for i in range(n + 1)] for j in range(n + 1)]

    for f in fares:
        x, y, z = f
        graph[x][y] = graph[y][x] = z

    for k in range(1, n + 1):
        for x in range(1, n + 1):
            for y in range(1, n + 1):
                graph[x][y] = min(graph[x][y], graph[x][k] + graph[k][y])

    ans = graph[s][a] + graph[s][b]
    for i in range(1, n + 1):
        ans = min(ans, graph[s][i] + graph[i][a] + graph[i][b])
    return ans;

플로이드-워셜 

플로이드-워셜 알고리즘 실행 후

s 에서 a,b 까지의 거리와 1 ~ n 지점을 거쳐간 거리의 합 중 최소가 되는 값을 결과로 리턴