백준 23354 - 군탈체포조 (C++)

문제 문제 링크 BOJ 23354 - 군탈체포조 문제 요약 격자의 정보가 주어진다. 탈영병을 모두 잡고 부대로 복귀하는 최소 비용을 구해보자.

제한 TL : $3$ sec, ML : $512$ MB $5 ≤ N ≤ 1,000 $1 ≤ N_{i,j} ≤ 1,000$ 탈영병의 수는 $5$ 이하 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 브루트포스 알고리즘(bruteforcing) 풀이 탈영병의 수만큼 다익스트라를 돌려 임의의 탈영병 위치에서 다른 탈영병 위치로의 최단 거리를 모두 구해주자. 그럼 답은 (탈영병을 최소로 순회하는 비용) + (첫번째 탈영병과 부대와의 거리) + (마지막 탈영병과 부대와의 거리) 이 된다.

탈영병의 수가 $5$로 굉장히 작아 모든 경우를 돌려보면 된다......