7190 : 치킨 배달
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
도시의 정보가 격자판으로 주어집니다. 각 칸은 빈칸(0), 집(1), 치킨집(2)입니다. 도시의 치킨집 중 최대 M개만 남겨두고 나머지는 폐업시키려고 할 때, 도시의 치킨 거리의 최솟값을 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 N과 M이 주어집니다. (2 ≤ N ≤ 50, 1 ≤ M ≤ 13)
둘째 줄부터 N개의 줄에 걸쳐 도시의 정보(N×N)가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 도시의 정보(N×N)가 공백으로 구분되어 주어집니다.
출력 설명
M개의 치킨집을 남겼을 때 얻을 수 있는 도시의 치킨 거리의 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
치킨집 3개를 모두 선택하면 각 집과의 최소 거리 합(치킨 거리)은 5가 됩니다.