[BOJ]10217번: KCM Travel

 

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

---

바킹독님 풀이를 통해서 해결했습니다. (https://blog.encrypted.gg/164)

 

DP[i][j]: "1번 노드부터 i번 노드까지 비용 j를 써서 갈 때의 최소 시간"으로 상태를 정의합니다.

 

예외 조건은 j 값이 M을 초과하면 예외입니다. (continue)

 

이렇게 상태를 정의하고 1번 노드부터 다익스트라를 돌리면, 

"비용 M 이하" 조건을 만족하는 경로 중에서 가장 먼저 N번 노드에 도착하는 경로가 최소 시간을 만족하는  정답입니다.

---

https://github.com/cottory/algorithm/blob/master/BOJ/BOJ10217.cc