https://www.acmicpc.net/problem/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])
'Problem Solving > 최단 경로' 카테고리의 다른 글
BOJ1916 최소비용 구하기 (0) | 2023.03.30 |
---|---|
BOJ18352 특정 거리의 도시 찾기 (0) | 2023.03.20 |
전보 (1) | 2023.01.20 |
미래도시 (0) | 2023.01.19 |