Informatica Online Judge

  최소비용신장트리(MST) [1383 / 0567]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 137   Total Tried : 158


The Champion of this Problem (C++) : gs140742 - ms / 606byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

N개의 섬이 주어진다.

모든 섬에서 다른 섬으로 이동할 수 있도록 하기 위해서 각 섬들을 연결하는 다리를 건설할 계획을 세웠다.

다리를 연결할 수 있는 경우는 M가지가 주어지고, 각 M가지를 건설하는 비용이 주어진다.

주어진 비용을 이용하여 최소의 값을 들여서 목적을 달성할 수 있는 프로그램을 작성하시오.



주어진 그림의 경우 1-2, 2-4, 4-3, 4-6, 6-7, 7-5를 연결하는 다리를 건설하면 비용이 229가 들며, 이보다 더 적게 쓰는 방법은 없다.

Input

첫째 줄에는 한 칸씩의 공백을 두어 지역의 수와 한 지역에서 다른 지역으로 가는 총 방법의 수가 주어지며 두 번째 줄부터 M+1줄까지는 한 칸씩의 공백을 두어 각 섬과 그 섬을 연결하는 다리를 만드는데 드는 비용이 주어진다.

루프간선이 있을 수 있으며, 멀티간선이 있을 수 있으니 주의!!

[입력값의 정의역]
1 <= N <= 500
0 <= M <= 10,000

Output

다리를 건설하는데 드는 최소 비용을 출력한다.
만약 만들 수 없다면 "Impossible"를 첫째 줄에 출력한다.(단, 큰따옴표는 출력하지 않는다)

IO Example

입력
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

출력
229

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]