백준 1446 지름길 Python

🐸 문제 정보

1446번: 지름길

 

🤖 알고리즘

다익스트라

 

⏱️ 풀이 시간

30.05m

 

📝 풀이

최근에 공부한 최단거리 포스팅을 읽어보면 쉽게 풀 수 있는 문제였다.

모든 거리 지점을 노드라고 생각하고, 각 지점에서 다음 지점까지 가중치 1씩을 기본으로 설정했다.

그리고 지름길이 있는 부분에 간선을 추가하여 다익스트라를 돌리면 되는 문제였다.

 

최단 경로 찾기 with Python

 

뭔가 뿌듯했다.. 나 이제 최단 경로 찾기 잘할수있숴

 

🧑‍💻 나의 답

# pypy3

import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize

n, d = list(map(int, input().rstrip().split()))
graph = [[(i + 1, 1)] if i < d else [] for i in range(d + 1)]
distance = [INF] * (d + 1)

for _ in range(n):
    u, v, m = list(map(int, input().rstrip().split()))
    if u > d: continue
    if v > d: continue
    graph[u].append((v, m))
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # 우선 순위, 현재 지점
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist: continue
        for node in graph[now]:
            if dist + node[1] < distance[node[0]]:
                distance[node[0]] = dist + node[1]
                heapq.heappush(q, (dist + node[1], node[0]))

dijkstra(0)
print(distance[d])