[카카오 기출] 합승 택시 요금

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

코딩테스트 연습 - 합승 택시 요금

import sys
inf = sys.maxsize
def solution(n, s, a, b, fares):
    table = [[inf]*n for _ in range(n)]
    for i in range(n):
        table[i][i] = 0
        
    for i in range(len(fares)):
        c, d, cost = fares[i]
        table[c-1][d-1] = cost
        table[d-1][c-1] = cost
        
    for i in range(n):
        for j in range(n):
            for k in range(n):
                table[j][k] = min(table[j][k], table[j][i]+ table[i][k])

    answer = 0   
    # not together
    answer = table[a-1][s-1] + table[b-1][s-1]
    
    for i in range(n):     
        cur_cost = table[s-1][i] + table[i][a-1] + table[i][b-1]
        answer = min(answer, cur_cost)
        
    return answer