BOJ1446 지름길

 

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

1446번: 지름길

난이도: 실버1

소요시간:45분

관련 알고리즘: 다익스트라(데이크스트라)

 

DFS,BFS,다익스트라,이분검색은 조금 더 익숙해질 필요가 있는 것 같다. 예상치 못하게 오류를 만나 시간을 많이 소비했다. 

손에 익어서 깊게 생각안하고도 구현할 정도로 연습을 해야겠다.

 

아래는 나의 코드다. 고속도로는 전부 이어져 있기 때문에 거리값을 1,2,3,...으로 초기화 했다. 그리고 i+1노드와 전부 이어져 있기에 연결통로도 graph에 전부 추가하여 이어주었다. 그후 다익스트라를 진행했다. 지름길 끝점이 고속도로 끝보다 길면 필요가 없기에 입력부분에서 걸러주었다.

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])