[프로그래머스]배달(Python) - 다익스트라
https://programmers.co.kr/learn/courses/30/lessons/12978
다익스트라 문제.
# 프로그래머스 Summer/Winter Coding(~2018) 배달 - 2단계
import heapq
def solution(N, road, K):
answer = 0
graph = [[] for _ in range(N + 1)]
dis = [int(1e9)] * (N + 1)
for i in range(len(road)):
a, b, w = road[i]
graph[a].append((b, w))
graph[b].append((a, w))
Q = []
heapq.heappush(Q, (0, 1))
dis[1] = 0
while Q:
dist, now = heapq.heappop(Q)
if dis[now] < dist:
continue
for node in graph[now]:
cost = dist + node[1]
if cost < dis[node[0]]:
dis[node[0]] = cost
heapq.heappush(Q, (cost, node[0]))
for i in range(1, N + 1):
if dis[i] <= K:
answer += 1
return answer
solution(5, [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]], 3)
Author And Source
이 문제에 관하여([프로그래머스]배달(Python) - 다익스트라), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@smkim104/프로그래머스배달Python-다익스트라저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)