✓

태그:

26. 동적 계획법과 최단거리 역추적 CLASS 4

최단 거리는 역시 D읍읍 2

풀이 비스무리한거 보기

N개의 도시와 M개의 버스와 그 비용이 주어졌을 때, 주어지는 시작점으로부터 주어지는 도착점까지 최소의 비용과 그 경로를 구하는 문제입니다. ⑤ 1916 - 최소비용 구하기 문제와 같이 역시 시작점이 정해진 최소 비용(최단 거리) 문제는 다익스트라입니다. 다익스트라를 사용해서 구하되, 그래프를 굳이 다 탐색할 필요는 없습니다. 판별하는 점이 도착점이면 이미 해당 점까지의 최단 거리는 구해져있으므로 여기서 탐색을 끊고 답을 출력할 수 있습니다.

거리야 뭐 쉽게 구할 수 있다만 경로는 어떻게 구하지 하신다면 다익스트라를 다시 검색해보시는 것을 추천합니다. 다익스트라 알고리즘은 경로까지 구하게 되어있더군요.(저도 처음 알았습니다)

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-03 23:09:18

---