[프로그래머스] 합승 택시 요금 Python

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

프로그래머스

 

 

import heapq 

INF = int(1e9)

def dijkstra(n, start, graph): # end : a or b 
    distance = [INF]*(n+1)
    distance[start] = 0 
    queue = []
    heapq.heappush(queue, (0, start)) 
    while queue:
        dist, now = heapq.heappop(queue)
        if dist < distance[now]:
            continue 
        for next, next_dist in graph[now]:
            if next_dist + dist < distance[next]:
                distance[next] = next_dist + dist 
                heapq.heappush(queue, (next_dist + dist, next))
    return distance
    
    
def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n+1)]
    answer = INF
    
    for x, y, cost in fares:
        graph[x].append((y, cost))
        graph[y].append((x, cost))
    
    every_distance = [[]]
    for i in range(1, n+1):
        every_distance.append(dijkstra(n, i, graph))
    
    # 현재 지점을 거치는 방법 vs 거치지 않는 방법을 비교 
    for i in range(1, n+1):
        answer = min(answer, every_distance[s][i] + every_distance[i][a] + every_distance[i][b])
    return answer