[백준 / BOJ] 1162 도로포장

문제

1162번: 도로포장

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하

www.acmicpc.net

도시의수 N, 도로의수 M, 포장할 도로의수 K가 주어진다.

M개의 도로를 K만큼 포장할수있고, 포장한 도로의 비용은 0이될때, 최소비용을 구하는 문제다.

2206 벽 부수고 이동하기 와 비슷한 느낌의 문제였다.

다익스트라로 풀었는데, 포장횟수가 20까지밖에 안주어지므로 모든경우를 다 봐줘도 시간초과가 나지않는다.

check배열을 2차원으로 만들어서, 체크해줬다.

check[방문idx][현재까지 도로 포장횟수] = 비용;

구현은 체크배열이 2차원인점 제외하고 기본 다익스트라와 똑같다

탐색시,

1. 현재 위치에서 다음 위치로 도로를 포장하고 가는경우

2. 현재 위치에서 다음 위치로 도로를 포장하지않고 그냥 가는경우

2가지 경우를 봐주며 탐색하고 도착지에 도달했을때, 1~20까지의 경우를 봐주고 가장작은값을 출력해주면 답이다.

devxb/JJUNalgo

백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.

github.com