Informatica Online Judge

  파이프 개선 장치 [1963 / 07AB]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 1   Total Tried : 8


The Champion of this Problem (C++) : gs17068 - 37ms / 4698byte
My Best Submission (C++) : N/A

[CCC 2017]

Background

어떤 도시에는 $1, 2, ... , n$ 번 건물이 있고, $m$개의 하수도 파이프가 빌딩 사이에 연결되어있다.

하지만, 도시 계획이 잘못 되어 1번 건물에만 하수도 처리 시설이 설치되어있다. 건물들 사이에 연결되어있는 각각의 하수도 파이프를 잠그거나 열 수 있다.

파이프들을 잠그거나 열어 적당한 도시 하수도 처리 계획이 수행될 수 있는데, $1$번 건물에 직간접적으로 다른 건물들이 연결되어야 한다. (두 건물 사이의 파이프를 열면 직접 연결되는 것이고, 다른 건물을 거쳐 연결되면 간접적으로 연결되는 것이다.)

그 도시의 지방자치정부는 $n-1$개의 파이프만 열어 도시 하수도 처리 계획을 수행할 수 있도록 만들고 싶어 한다. 하지만, 너무 많은 비용이 들어가는 것이 아닐지 우려하고 있다! 파이프들을 열면 관리비가 매달 들어가게 된다.

경곽 학생들은 R&E 연구를 통해 파이프 효율 개선 장치를 만들었는데, 그렇게 만든 장치를 이용해 $1$개 파이프의 관리비를 줄일 수 있다.

어떤 파이프의 매달 관리비가 $c$라고 하고, 효율 개선 장치의 개선 효과를 $d$라고 하면, 그 효율 개선 장치가 설치된 파이프의 관리비는 $max(0, c-d)$가 된다.

도시 정부는 도시 하수도 처리 계획을 수행하는데 필요한 비용을 최소화하고, 최대한 빨리 그 계획을 실행하고 싶어 한다.

하루에 $1$개의 파이프를 열고, $1$개의 파이프를 잠글 수 있다.

최소 비용의 하수도 처리 계획을 수행하기 위해 필요한 준비는 며칠 만에 가능할까? $1$개의 파이프 효율 장치를 사용할 수 있다.

Input

첫 줄에는 건물 개수($n$), 파이프 연결 개수($m$), 효율 개선 장치 효과($d$)가 공백을 두고 입력된다.

그 다음 $m$개의 줄에는 파이프가 연결되는 $2$개의 건물번호($A_i, B_i$)와 파이프 사용 비용($c_i$)이 공백을 두고 입력되고, 이 중 위에서부터 순서대로 $n-1$개는 현재 열려 있는 파이프들이다.(두 건물 사이에는 적어도 1개 이상의 파이프가 연결되어있고, 건물 자신으로 다시 연결되는 파이프는 없다.)


[입력값의 정의역]

$1≤n≤100,000$
$n-1≤m≤200,000$
$0≤d≤10^9$
$1≤A_i, B_i≤n$
$1≤c_i≤10^9$

Output

하수도 처리 계획을 최소비용으로 수행할 수 있도록 조정하는데 필요한 최소 날 수를 출력한다.

IO Example

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

출력1
1

설명 : 파이프 개선 효과(d)가 없다. 2-3을 닫고 4-1을 열어 하루 만에 최소 관리비 상태로 바꿀 수 있다.

입력2
5 6 2
1 2 5
2 3 5
1 4 5
4 5 5
1 3 1
1 5 1

출력2
2

설명 : 1-2에 장치를 붙여 비용을 3으로 만들고, 첫 날 2-3으로 연결된 파이프를 잠그고 1-3 파이프를 연다. 두 번째 날 1-4 파이프를 잠그고 1-5 파이프를 연다. 전체 관리비용이 10이 되고 최소가 된다. 만약, 1-3 이나 1-5 파이프에 개선 장치를 붙이면 그 파이프의 관리비는 0이 되지만 그렇게 되면 전체 관리비용을 11보다 작게 만들 수 없다.

입력3
4 4 0
1 2 2147483647
2 3 2147483647
3 4 2147483647
4 1 2147483649

출력3
0

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