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

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

프로그래머스

 

 

 

정확성 테스트

테스트 1 〉	통과 (0.04ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.5MB)
테스트 4 〉	통과 (0.15ms, 10.1MB)
테스트 5 〉	통과 (0.07ms, 10.4MB)
테스트 6 〉	통과 (0.08ms, 10.2MB)
테스트 7 〉	통과 (0.09ms, 10.3MB)
테스트 8 〉	통과 (0.10ms, 10.3MB)
테스트 9 〉	통과 (0.11ms, 10.2MB)
테스트 10 〉	통과 (0.19ms, 10.3MB)

효율성 테스트

테스트 1 〉	통과 (1.45ms, 10.4MB)
테스트 2 〉	통과 (3.80ms, 10.6MB)
테스트 3 〉	통과 (1.04ms, 10.4MB)
테스트 4 〉	통과 (1.42ms, 10.3MB)
테스트 5 〉	통과 (1.19ms, 10.3MB)
테스트 6 〉	통과 (1.06ms, 10.3MB)
테스트 7 〉	통과 (26.81ms, 14.4MB)
테스트 8 〉	통과 (27.36ms, 14.8MB)
테스트 9 〉	통과 (25.11ms, 14.4MB)
테스트 10 〉	통과 (26.27ms, 14.5MB)
테스트 11 〉	통과 (45.76ms, 14.4MB)
테스트 12 〉	통과 (26.68ms, 12.5MB)
테스트 13 〉	통과 (14.53ms, 12.5MB)
테스트 14 〉	통과 (14.16ms, 12.4MB)
테스트 15 〉	통과 (15.69ms, 12.4MB)
테스트 16 〉	통과 (0.90ms, 10.2MB)
테스트 17 〉	통과 (1.17ms, 10.3MB)
테스트 18 〉	통과 (1.57ms, 10.2MB)
테스트 19 〉	통과 (2.38ms, 10.5MB)
테스트 20 〉	통과 (4.38ms, 10.7MB)
테스트 21 〉	통과 (4.31ms, 10.6MB)
테스트 22 〉	통과 (15.31ms, 12.4MB)
테스트 23 〉	통과 (15.30ms, 12.5MB)
테스트 24 〉	통과 (14.11ms, 12.4MB)
테스트 25 〉	통과 (1.38ms, 10.3MB)
테스트 26 〉	통과 (1.17ms, 10.4MB)
테스트 27 〉	통과 (6.35ms, 10.5MB)
테스트 28 〉	통과 (3.74ms, 10.6MB)
테스트 29 〉	통과 (0.64ms, 10.3MB)
테스트 30 〉	통과 (1.09ms, 10.3MB)

채점 결과

정확성: 50.0

효율성: 50.0

합계: 100.0 / 100.0

 

 

import heapq

def solution(n, s, a, b, fares):
    answer = 0
    # 도로 제작(딕셔너리 형태)
    dic_moveable = {}
    set_node = set()
    for fare in fares:
        set_node.add(fare[0])
        set_node.add(fare[1])
        if fare[0] in dic_moveable:
            dic_moveable[fare[0]].update({fare[1]: fare[2]})
        else:
            dic_moveable[fare[0]] = {fare[1]: fare[2]}

        if fare[1] in dic_moveable:
            dic_moveable[fare[1]].update({fare[0]: fare[2]})
        else:
            dic_moveable[fare[1]] = {fare[0]: fare[2]}

    def dijkstra(graph, start):
        distance = {node: float('inf') for node in graph}
        distance[start] = 0
        
        queue = [(0, start)]
        
        while queue:
            current_distance, current_node = heapq.heappop(queue)
            
            if current_distance > distance[current_node]:
                continue
            
            for neighbor, weight in graph[current_node].items():
                distance_to_neighbor = current_distance + weight
                
                if distance_to_neighbor < distance[neighbor]:
                    distance[neighbor] = distance_to_neighbor
                    heapq.heappush(queue, (distance_to_neighbor, neighbor))
        
        return distance

    # 다익스트라 알고리즘을 사용하여 특정 노드까지의 거리 계산
    s_distances = dijkstra(dic_moveable, s)
    a_distances = dijkstra(dic_moveable, a)
    b_distances = dijkstra(dic_moveable, b)
    tm = 0

    for node in set_node:
        tm = s_distances[node] + a_distances[node] + b_distances[node]
        if answer == 0 or answer > tm:
            answer = tm
    
    return answer