마법 도서관 탐험
골드 V의견: 0
마법사 아리는 \(N\)개의 신비로운 도서관을 순서대로 방문하는 탐험을 계획하고 있다. 도서관은 \(1\)번부터 \(N\)번까지 번호가 붙어 있고, 아리는 반드시 도서관 \(1\)번에서 출발하여 \(N\)개의 도서관을 모두 정확히 한 번씩 방문해야 한다. 마지막 도서관은 어디여도 상관없다.
\(i\)번 도서관에서 \(j\)번 도서관으로 이동하는 데 드는 마법 비용 \(d_{i,j}\)가 주어질 때, 모든 도서관을 방문하는 최소 비용을 구하여라. (\(i \neq j\)이면 \(d_{i,j}\)는 양의 정수이며, \(d_{i,i} = 0\)이다.)
같은 도서관을 두 번 이상 방문하면 비용이 추가로 발생하고 모든 도서관을 방문하지 못할 수 있으므로, 반드시 각 도서관을 정확히 한 번만 방문해야 한다.
- \(1 \le N \le 15\)
- \(d_{i,i} = 0\)
- \(i \neq j\)이면 \(1 \le d_{i,j} \le 10\,000\)
첫째 줄에 도서관의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에 이동 비용 \(d_{i,1},\ d_{i,2},\ \ldots,\ d_{i,N}\)이 공백으로 구분되어 주어진다. \(d_{i,i} = 0\)이고 \(i \neq j\)이면 \(1 \le d_{i,j} \le 10\,000\)이다.
모든 도서관을 정확히 한 번씩 방문하는 최소 마법 비용을 출력한다.
3
0 3 10
3 0 2
10 2 0
5
도시 \(1 \to 2 \to 3\) 경로의 비용은 \(3 + 2 = 5\)이고, 다른 경로 \(1 \to 3 \to 2\)는 \(10 + 2 = 12\)이므로 최솟값은 \(5\)이다.
4
0 1 100 100
1 0 1 100
100 1 0 1
100 100 1 0
3
경로 \(1 \to 2 \to 3 \to 4\)의 비용이 \(1 + 1 + 1 = 3\)으로 최소이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 도서관 탐험
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 도서관 탐험