BOJ1446 링크

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

난이도: 실버 1

소요 시간: 45분

관련 알고리즘: Dijkstra(Dijkstra)

DFS, BFS, Dijkstra 및 Binary Search는 조금 더 친숙해야 하는 것 같습니다. 예기치 않게 오류가 발생하여 시간이 많이 걸렸습니다.

익숙해졌기 때문에 별 생각 없이 할 수 있을 만큼 충분히 연습해야 한다.

아래는 제 코드입니다. 고속도로가 모두 연결되어 있기 때문에 거리 값은 1,2,3,… 그리고 모두 i+1 노드에 연결되어 있기 때문에 다이어그램에 모든 연결 통로를 추가하여 연결했습니다. 그런 다음 Dijkstra가 수행되었습니다. 지름길의 끝이 고속도로의 끝보다 긴 경우 이는 필수가 아니므로 입력 부분에서 필터링됩니다.

import sys
import heapq
N,D= map(int,sys.stdin.readline().split())
dist=(i for i in range(D+1))
graph=(((1,i+1)) for i in range(D+1))
graph(D)=()

for i in range(N):
    start,end,length = map(int,sys.stdin.readline().split())
    if start<=D and end<=D:
        graph(start).append((length,end))


def dijkstra(start):
    hq=()
    dist(start)=0
    heapq.heappush(hq,(0,start))
    while hq:
        distance,node = heapq.heappop(hq)
        for next_length,next_node in graph(node):
            if next_length + distance <= dist(next_node):
                dist(next_node)=next_length+distance
                heapq.heappush(hq,(dist(next_node),next_node))

dijkstra(0)
print(dist(D))