7218 : 최적 경로 완전탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
그리드 도시의 도로 이동 비용 격자가 주어집니다. 집에서 출발하여 마트를 경유해 학교로 도달할 때 지나간 칸들의 비용 합의 최솟값(최단 경로)을 구하십시오. (상하좌우 이동이 가능합니다.)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 그리드 도시의 크기 N, M이 주어집니다. (1 ≤ N, M ≤ 10)
둘째 줄에 집, 마트, 학교의 좌표(행, 열) 6개가 공백으로 구분되어 주어집니다.
셋째 줄부터 N개의 줄에 걸쳐 도로의 가중치 비용(N×M)이 주어집니다.
둘째 줄에 집, 마트, 학교의 좌표(행, 열) 6개가 공백으로 구분되어 주어집니다.
셋째 줄부터 N개의 줄에 걸쳐 도로의 가중치 비용(N×M)이 주어집니다.
출력 설명
최소 가중치 경로 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 1 2 2 3 3
1 2 3
4 5 6
7 8 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
23도움
집(1,1) → 마트(2,2) → 학교(3,3) 경로 비용의 최소합입니다. 다익스트라로 각 구간 최단거리를 구합니다.