[▲][다익스트라] 1446번 지름길 - python, 실버1

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

 

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

 

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

 

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

 

---

 

이문제의 핵심은

 

출발지점에서 도착지점까지 가는데

 

지름길 정보가 없으면 다음 (+1)가는걸 저장한 이후,

지름길 정보를 저장한다는것!

 

 

 

 

💻 내가 쓴 정답코드

import heapq
import sys
input = sys.stdin.readline

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 i in graph[now]:
            #i[0] 길/지름길 도착지점
            #i[1] 길/지름길 길이
            cost = dist + i[1] #현재 지점에서 길/지름길을 더함 

            #해당 노드로 가는데 계산된 비용이 최단거리테이블보다 작으면 업데이트
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    
n, d = map(int,input().split())

INF = int(1e9)

distance = [INF]*(d+1)
graph = [[] for _ in range(d+1)]

for i in range(d):
    graph[i].append((i+1,1))

for _ in range(n):
    start, end , length = map(int, input().split())
    
    if end > d: 
        continue
    
    #지름길 정보 입력
    graph[start].append((end, length))

dijkstra(0)
print(distance[d])

 

 

 

다익스트라를 복습하고 코드를 다시 익히려고 푼 문제인데

다익스트라 관련되어서 문제를 좀더 풀어봐야 익숙해질것 같다.

 

 

다익스트라는 한 노드에서 전체 노드에 가는 최단거리!!

플로이드워셜은 전체노드에서 전체노드에 가는 최단거리!!!

 

플로이드도 오늘 한번 더 봐야겠다.