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

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

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

 

매 지점까지 같이 합승했다고 치고 그 지점에서 각자 목적지로 이동했을 경우에서 요금을 모두 더한 값이 최소가 될 때 정답으로 추가했다.

각자 목적지로 이동하는 것은 다익스트라 알고리즘을 구현했다.

 

나의 풀이

import heapq

def dijkstra(start,distance,graph):
    heap = []
    distance[start] = 0
    heapq.heappush(heap,(0,start))
    while heap:
        dist, now = heapq.heappop(heap)
        if dist > distance[now]:
            continue
        else: distance[now] = dist
        for dest in graph[now]:
            heapq.heappush(heap,(dist+dest[1],dest[0]))
    return distance
def solution(n, s, a, b, fares):
    INF = int(1e9)
    minimun_fare = INF
    graph = [[] for _ in range(n+1)]
    distance = [INF for _ in range(n+1)]
    for fare in fares:
        graph[fare[0]].append((fare[1],fare[2]))
        graph[fare[1]].append((fare[0],fare[2]))

    distance = dijkstra(s,distance,graph)
    for start in range(1,n+1):
        dist = [INF for _ in range(n+1)]
        dist = dijkstra(start,dist,graph)
        minimun_fare = min(minimun_fare,distance[start]+dist[a]+dist[b])
    return minimun_fare

오랜만에 한번에 풀어서 기분이 좋았당