19297번 - Logistical Metropolis 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 218 | 57 | 43 | 26.380% |
문제
우주제국의 황제 명우는 최근 서로 전쟁을 하던 $N$개 행성을 어부지리로 점령했다. 이제 이 $N$개의 행성에는 평화가 찾아왔다.
여기에 더해서 명우는 $N$개 행성 간에 서로 이동이 가능하도록 $N-1$쌍의 워프 게이트를 설치하려고 한다. 하나의 워프 게이트를 설치하면 두 행성 간의 이동이 가능하며, 어떤 행성들을 어떤 방식으로 연결하느냐에 따라 비용의 차이가 있을 수 있다. 명우는 현재 총 $M$가지 쌍의 워프 게이트를 연결할 수 있다.
명우는 $N$개의 행성 중 하나를 골라 주요 행성으로 삼아 자신의 우주 제국과 연결되는 워프 게이트를 만들 것이다. 명우는 선택된 주요 행성과 연결되는 워프 게이트를 비용을 따지지 않고 최대한 많이 만들고 싶다. 각각의 행성을 주요 행성으로 삼을 때 $N-1$개의 워프 게이트를 설치하는 비용의 최솟값을 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 두 정수 $N$, $M$($1 ≤ N ≤ 100\,000$, $N-1 ≤ M ≤ 300\,000$)이 공백 하나로 구분되어 주어진다.
다음 $M$개 줄의 각 줄에는 건설 가능한 워프 게이트의 정보를 나타내는 세 정수 $x$, $y$, $c$($1 ≤ x < y ≤ N$, $1 ≤ c ≤ 10^9$)가 공백 하나로 구분되어 주어진다. 이는 $x$번 행성과 $y$번 행성을 잇는 워프 게이트를 건설하기 위해 비용이 $c$ 필요하다는 뜻이다. 같은 두 행성에 대한 정보는 여러 번 주어지지 않는다. 모든 워프 게이트를 건설하면, 모든 두 행성간 이동이 가능한 것이 보장된다.
출력
$N$개의 줄에 걸쳐 정답을 출력한다. $i$번째 줄에는 $i$번 행성을 주요 행성으로 삼을 때, 모든 행성간 이동이 가능하도록 $N-1$개의 워프 게이트를 설치하는 비용의 최솟값이 출력되어야 한다.
예제 입력 1
4 4 1 2 1 2 3 2 3 4 3 1 4 4
예제 출력 1
7 6 6 8
출처
Camp > Petrozavodsk Programming Camp > Winter 2018 > Day 5: Grand Prix of Korea G번
Contest > kriiicon > 제5회 kriiicon LM번
Contest > Open Cup > 2017/2018 Season > Stage 10: Grand Prix of Korea G번
- 문제를 만든 사람: august14
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호