본문 바로가기
Algorithm/BOJ

[BOJ]1162번: 도로포장

by BAYABA 2020. 7. 29.

 

문제: 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/cottory/algorithm/blob/master/BOJ/BOJ1162.cc

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ]16397번: 탈출  (0) 2020.08.06
[BOJ]9019번: DSLR  (0) 2020.07.30
[BOJ]5719번: 거의 최단 경로  (0) 2020.07.28
[BOJ]2096번: 내려가기  (0) 2020.07.22
[BOJ]17135번: 캐슬 디펜스  (0) 2020.07.22