합승 택시 요금

jiholee·2022년 1월 17일
0

알고리즘

목록 보기
8/20

합승 택시 요금

사용한 알고리즘: 플로이드 워셜

def solution(n, s, a, b, fares):
    answer = 1e9
    INF = int(1e9)
    dist = [[1e9] * (n+1) for _ in range(n+1)]  # 최단 거리 저장 배열
    
    for fare in fares:
        c, d, f = fare
        dist[c][d] = f
        dist[d][c] = f
    
    for i in range(1, n+1):
        dist[i][i] = 0
    
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    for k in range(1, n+1):
        answer = min(answer, dist[s][k] + dist[k][a] + dist[k][b])
    return answer

0개의 댓글