22278번 - 두 최단 경로 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 71 | 11 | 10 | 22.222% |
문제
$N$ 개의 정점과 $M$ 개의 간선이 있는 그래프가 있다. 각 간선에는 방향성이 있으며, 음이 아닌 정수 가중치를 가진다.
모든 $2 \le i \le N$ 에 대해서, 1번 정점에서 $i$ 번 정점으로 가는 두 개의 겹치지 않는 경로들 중, 비용 합의 최솟값을 계산하라. 경로가 겹치지 않는다는 것은, 같은 간선을 공유하지 않는다는 것이다. 경로의 비용은, 경로에 속하는 간선의 가중치를 전부 합한 값이다.
입력
첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.
- 첫 번째 줄에 정수 $N, M$이 주어진다.
- 이후 $M$ 개의 줄에 세 정수 $u_i, v_i, w_i$ 가 주어진다. $u_i$ 번 정점에서 $v_i$ 번 정점으로 가는 가중치 $w_i$ 의 간선이 존재한다는 뜻이다.
출력
각 테스트 케이스 마다 한 줄에 $N-1$ 개의 정수를 출력하라. 이 중 $i$ 번째 정수는, 1번 정점에서 $i+1$ 번 정점으로 가는 두 개의 겹치지 않는 경로들 중, 비용 합의 최솟값을 뜻한다. 만약 두 개의 겹치지 않는 경로가 존재하지 않는다면 -1을 출력하라.
제한
- $1 \le u_i , v_i \le N$
- $u_i \neq v_i$
- $i \neq j \iff (u_i, v_i) \neq (u_j, v_j)$
- $0 \le w_i \le 10^9$
- 1번 정점에서 모든 정점으로 도달할 수 있다.
- 한 입력 파일에 대해, $N$ 의 합은 $100\,000$ 이하이다.
- 한 입력 파일에 대해, $M$ 의 합은 $1\,000\,000$ 이하이다.
예제 입력 1
3 3 4 1 2 1 1 3 2 2 3 3 3 2 4 2 2 1 2 1 2 1 0 5 7 1 2 4 2 3 3 1 3 8 3 5 3 4 5 2 5 4 7 1 5 1
예제 출력 1
7 6 -1 -1 15 -1 11
예제 입력 2
2 4 9 1 2 18 2 3 1 3 4 11 4 3 2 4 1 30 3 1 24 3 2 22 1 3 18 2 4 1 4 5 1 2 2 1 3 14 1 4 4 2 1 20 2 3 30
예제 출력 2
58 37 48 -1 46 -1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호