프로그래머스 - 합승 택시 요금

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/72413

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

 

 

플로이드 와샬 문제!

 

 

 

from copy import deepcopy

def solution(n, s, a, b, fares):
    answer = float('inf')
    
    def floyd_warshall(adj):
        length = len(adj)
        ret = [x.copy() for x in adj]
        
        for k in range(length):
            for i in range(length):
                for j in range(length):
                    if ret[i][k] + ret[k][j] < ret[i][j]:
                        ret[i][j] = ret[i][k] + ret[k][j]
        
        return ret
        
    
    adj = [[float('inf') for _ in range(n)] for _ in range(n)]
    
    for u, v, fee in fares:
        adj[u - 1][v - 1] = fee
        adj[v - 1][u - 1] = fee
    for i in range(n):
        adj[i][i] = 0
    
    
    min_path = floyd_warshall(adj)
    
    
    for waypoint in range(n):
        total_fee = min_path[s - 1][waypoint] + min_path[waypoint][a - 1] + min_path[waypoint][b - 1]
        if total_fee != float('inf'):
            answer = min(answer, total_fee)
    
    return answer

 

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~