프로그래머스 합승 택시 요금 파이썬

1. 문제

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

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

 

 

2. 풀이

다익스트라

 

3. 구현

import math
import heapq
    
def solution(n, s, a, b, fares):
    answer = 0
    
    gph=[[] for _ in range(n+2)]
    for f in fares:
        [curs,cure,curw] = f
        gph[curs].append((cure,curw))
        gph[cure].append((curs,curw))
    
    answer_lis=[]
    for i in range(1, n+1):
        dist=[math.inf for _ in range(n+2)]
        edges=[]
        
        dist[i] = 0
        heapq.heappush(edges, (dist[i], i))
        
        while edges:
            cost,pos = heapq.heappop(edges)
            if dist[pos]<cost:
                continue
            for p,c in gph[pos]:
                c+=cost
                if dist[p]>c:
                    dist[p]=c
                    heapq.heappush(edges, (c,p))
        
        answer_lis.append(dist[a]+dist[b]+dist[s])
        
    return(min(answer_lis))

 

4. 테스트케이스 추가