네트워크 연결

면접 대비

시간 제한1초메모리 제한128 MB

요약
주어진 지점과 가중치가 있는 후보 케이블 경로들로 모든 지점을 연결하는 최소 총 케이블 길이를 구하는 문제입니다(최소 스패닝 트리).
난이도

쉬움10점 중 3점

유형
최소 신장 트리, 그래프, 유니온 파인드
정답자
아직 제출이 없습니다

문제

넓은 지역에 있는 특정 지점들을 잇는 네트워크 연결을 설계하려고 한다. 지역 안의 지점들의 집합과, 지점 쌍을 연결할 수 있는 케이블 경로들의 집합이 주어진다. 두 지점을 잇는 각 경로마다, 그 경로를 따라 두 지점을 연결하는 데 필요한 케이블의 길이가 주어진다. 두 지점 사이에 여러 개의 경로가 있을 수도 있음에 유의하라. 주어진 경로들은 지역 안의 임의의 두 지점을 (직접 또는 간접적으로) 연결한다고 가정한다.

임의의 두 지점 사이에 (직접 또는 간접적인) 연결이 존재하도록, 즉 모든 지점이 서로 연결되도록(반드시 직접 케이블로 연결될 필요는 없다) 하면서 사용하는 케이블의 총 길이가 최소가 되도록 네트워크를 설계하는 것이 문제이다.

입력

입력은 여러 개의 데이터 세트로 이루어지며, 각 데이터 세트는 하나의 네트워크를 정의한다. 각 데이터 세트의 첫째 줄에는 두 정수가 주어지는데, 첫 번째는 지점의 수 PP이고 두 번째는 지점들 사이 경로의 수 RR이다. 이어지는 RR개의 줄에는 각 경로가 세 정수로 주어진다. 앞의 두 정수는 두 지점을 나타내고, 세 번째 정수는 그 경로의 길이이다. 수들은 공백으로 구분된다. 하나의 수 P=0P = 0만으로 이루어진 데이터 세트는 입력의 끝을 나타낸다. 데이터 세트는 빈 줄로 구분된다.

지점의 수는 최대 5050개이다. 한 경로의 최대 길이는 100100이다. 가능한 경로의 수에는 제한이 없다. 지점은 11부터 PP까지(포함)의 정수로 구분된다. 두 지점 ii와 jj 사이의 경로는 i j 또는 j i로 주어질 수 있다.

출력

각 데이터 세트에 대해, 설계한 전체 네트워크에서 사용한 케이블의 총 길이를 한 줄에 하나의 수로 출력한다.

예제1

  1. 예제 1

    입력
    1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0
    예상 출력
    0
17
16
26