Informatica Online Judge

  도로건설 [2131 / 0853]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 0   Total Tried : 6


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs15098]

Background

도시 1~n을 연결할 수 있는 고속도로의 두 연결지점, 그리고 그 건설 비용이 주어져 있다. 도로의 사용 비용금은 건설 비용의 1억분의 1이다.

최대한 적은 비용으로 모든 도시를 연결하는 방법(임의의 서로 다른 두 도시 i, j 사이를 이동할수 있는 방법이 적어도 한 가지 존재하도록 하는 방법)으로 건설했을 때, 도시 1부터 n까지 이동하는데 드는 최소 비용을 구하시오

Input

첫 번째 줄에는 도시의 개수 n(3 이상 100 이하)와 건설 가능 도로 개수 m(3 이상 1000 이하)가 주어진다.

두 번째 줄부터 m+1번째 줄까지는 각각의 도로에 대한 양 끝 지점의 도시 번호, 그리고 건설 비용(1 이상 1000 이하)이 억 단위로 주어진다. (7 3 12 -> 7번 도시와 3번 도시를 잇는 도로는 건설하는데 12억 원이 소모됨)

Output

최대한 적은 비용으로 모든 도시를 연결하는 방법으로 연결망을 건설했을 때, 도시 1부터 n까지 이동하는데 드는 최소 비용을 출력한다.

IO Example

입력
4 4
1 4 2
1 2 1
2 3 1
3 4 1

출력
3

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