[다익스트라][Heap] 배달

배달

프로그래머스

 

 

 

import heapq

def dijkstra(start, graph, dist):
    queue=[]
    heapq.heappush(queue, (dist[start], start))
    
    while queue:
        cost, node= heapq.heappop(queue)
        for c, n in graph[node]:
            if cost+c>=dist[n]: continue
            dist[n]=cost+c
            heapq.heappush(queue, (dist[n], n))
        

def solution(N, road, K):
    answer = 0
    dist=[float('inf') for _ in range(N+1)]
    dist[1]=0
    graph=[[] for _ in range(N+1)]

    for rd in road:
        graph[rd[0]].append((rd[2], rd[1])) #거리, 도착지
        graph[rd[1]].append((rd[2], rd[0]))
    
    dijkstra(1, graph, dist)

    answer=len([d for d in dist if d<=K])
    return answer