rhtjdxo   1년 전

문제

넓은 지역의 특정 지점 간 네트워크 연결을 설계하도록 할당되었습니다. 해당 지역의 여러 지점과 한 쌍의 지점을 연결할 수 있는 케이블의 가능한 경로가 주어졌습니다. 두 지점 사이의 각 가능한 경로에 대해 해당 경로를 통해 지점을 연결하는 데 필요한 케이블의 길이가 주어집니다. 주어진 두 지점 사이에는 여러 가지 가능한 경로가 존재할 수 있습니다. 주어진 가능한 경로가 해당 지역의 각 두 지점을 직접 또는 간접적으로 연결한다고 가정합니다. 작업은 해당 지역의 네트워크를 설계하여 모든 지점이 직접 케이블로 연결되어 있지만 반드시 직접 케이블로 연결되는 것은 아니며, 사용된 케이블의 총 길이가 최소화되도록 설계하는 것입니다.

입력

입력 파일은 여러 데이터 세트로 구성됩니다. 각 데이터 세트는 하나의 필수 네트워크를 정의합니다. 세트의 첫 번째 줄에는 두 개의 정수가 포함되어 있습니다: 첫 번째 줄은 주어진 점의 수 P를 정의하고, 두 번째 줄은 점 사이의 주어진 경로의 수 R을 정의합니다. 다음 R 줄은 점 사이의 주어진 경로를 정의하며, 각각 세 개의 정수 번호를 제공합니다: 첫 번째 두 숫자는 점을 식별하고, 세 번째 숫자는 경로의 길이를 나타냅니다. 숫자는 공백으로 구분됩니다. 하나의 숫자 P=0만 제공하는 데이터 세트는 입력의 끝을 나타냅니다. 데이터 세트는 빈 줄로 구분됩니다.

최대 지점 수는 50개입니다. 주어진 경로의 최대 길이는 100개입니다. 가능한 경로의 수는 무제한입니다. 노드는 1과 P 사이의 정수로 식별됩니다(포함). 두 지점 i와 j 사이의 경로는 i j 또는 j i로 표시할 수 있습니다.

출력

각 데이터 세트마다 설계된 전체 네트워크에 사용되는 케이블의 총 길이를 나타내는 별도의 라인에 하나의 숫자를 인쇄합니다.

댓글을 작성하려면 로그인해야 합니다.