298. 합승 택시 요금

프로그래머스

1. Python

import sys
import heapq

def dijkstra(s, e):
    global graph, length
    
    distance = [sys.maxsize]*(length+1)
    distance[s] = 0
    pq = []
    heapq.heappush(pq, [0, s])
    while pq:
        cost, now = heapq.heappop(pq)
        
        if cost > distance[now]:
            continue
        
        for i in graph[now]:
            node, dist = i[0], i[1]

            dist += cost

            if dist < distance[node]:
                distance[node] = dist
                heapq.heappush(pq, [dist, node])
    
    return distance[e]

def solution(n, s, a, b, fares):
    global graph, length
    
    answer = sys.maxsize
    graph = [[] for _ in range(n+1)]
    length = n
    
    for i, j, cost in fares:
        graph[i].append([j, cost])
        graph[j].append([i, cost])
            
    for i in range(1, n+1):
        answer = min(answer, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b))
        
    return answer