우주 정거장 연결망
골드 V의견: 0
은하계에 \(N\)개의 우주 정거장이 있고, \(M\)개의 양방향 웜홀이 두 정거장을 연결하고 있다. 각 웜홀을 통과하는 데 걸리는 시간은 양의 정수로 주어진다. 같은 두 정거장을 잇는 웜홀이 여러 개 있을 수 있다.
모든 정거장 쌍 \((i, j)\) 사이의 최소 이동 시간 행렬을 출력하여라. 도달할 수 없는 쌍은 \(-1\)로 출력한다.
- \(1 \le N \le 100\)
- \(0 \le M \le \frac{N(N-1)}{2}\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10^9\)
첫째 줄에 정거장의 수 \(N\)과 웜홀의 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 웜홀의 양 끝 정거장 번호 \(u\), \(v\)와 통과 시간 \(w\)가 공백으로 구분되어 주어진다.
\(N\)개의 줄에 걸쳐 최소 이동 시간 행렬을 출력한다. \(i\)번째 줄의 \(j\)번째 수는 정거장 \(i\)에서 \(j\)까지의 최소 이동 시간이다. 도달 불가능하면 \(-1\)을 출력한다.
4 4
1 2 3
2 3 2
3 4 5
1 4 100
0 3 5 10
3 0 2 7
5 2 0 5
10 7 5 0
정거장 \(1\)에서 \(4\)까지 직접 가면 거리 \(100\)이지만, \(1\to2\to3\to4\) 경로는 \(3+2+5=10\)으로 더 짧다. 도달할 수 없는 쌍은 \(-1\)로 출력한다.
3 2
1 2 5
2 3 3
0 5 8
5 0 3
8 3 0
정거장 \(1\to3\)은 \(5+3=8\). 행렬 대각선은 모두 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
우주 정거장 연결망
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
우주 정거장 연결망