[BOJ]1162번: 도로포장(JAVA)

문제: https://www.acmicpc.net/problem/1162

---

JusticeHui님이 푸신 솔루션을 참고하여 해결하였습니다.

(출처: https://justicehui.github.io/usaco/2019/07/12/BOJ1162/)

 

도로 포장에 대한 정보를 어떻게 나타내느냐가 중요한 문제입니다.

 

이 문제의 경우 다익스트라의 결과값인 dist[N]을 다음과 같이 응용해서 정의할 수 있습니다.

 

dist[N][K]: 출발점 1번 도시에서 N번 도시까지 갈 때, K개의 도로를 포장해서 가는 최단거리.

 

이 때 저희가 원하는 정답 값은 아래와 같습니다.

 

answer = min(dist[N][0],dist[N][1],dist[N][2],dist[N][3],dist[N][4],...,dist[N][K])

---

코드: https://github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1162.java