문제
정올국엔 0번부터 (n-1)번까지 지정되어 있는 총 n개의 도시가 있다. 이는 m개의 양방향 도로로 연결되어 있다. 어떤 두 도시 i, j를 뽑더라도 i번 도시부터 j번 도시까지 직접 또는 다른 도시를 경유해서 가는 경로는 무조건 존재한다.
정올국의 대규모 도로 포장 정책으로, 모든 도로는 새것이 되었다. 그래서 초기에, 모든 도로의 부식도는 0이다. 화물 트럭이 한번 지나갈 때마다, 그 도로의 부식도는 1씩 증가한다.
정올국은 아직 t번의 도로 수리를 더 해줄 수 있는 예산이 있다. 한 번 수리할 때 마다, 도로의 부식도는 1씩 감소한다. 한 도로를 여러 번 수리하는 것도 가능하다.
화물 트럭의 내구도는 거쳐왔던 도로 중 가장 높은 부식도를 가진 도로의 부식도 만큼 감소한다. 내구도 감소가 클수록, 트럭의 질이 떨어진다.
철기는 정올 우체국택배의 매니저이다. 철기의 목표는 k개의 트럭을, 0번 도시부터 n-1번 도시까지 보내는 것이다. 철기는 k개의 트럭 중 내구도가 가장 많이 감소한 트럭의 내구도 감소가 최소화될 수 있도록 하고 싶다.
철기를 도와 k개의 트럭 중 최대로 내구도가 감소한 트럭이 최소의 피해를 입는 경우, 그 최대 내구도 감소도를 출력하는 프로그램을 작성하라.
입력
첫 줄에 네 정수인 n, m, k, t가 차례로 주어진다. n, m, k, t는 모두 1 이상 2,000 이하이다.
다음 m 줄에는 두 정수 u, v가 들어오며, 이는 u번 도시와 v번 도시 사이에 양방향 도로가 있다는 뜻이다.
u와 v는 모두 0이상 n 미만이다.
출력
가장 손상이 심한 트럭의 내구도 감소를 최소화시키는 경우, 그 트럭의 내구도 감소도를 출력한다.
예제 #1
7 8 2 0
0 1
0 2
1 3
2 3
3 4
3 5
4 6
5 6
0
예제 #2
5 5 2 1
0 1
1 2
1 3
2 4
3 4
0
예제 #3
4 4 10 0
0 1
1 3
0 2
2 3
4
힌트
출처
Hackerrank, Week Of Code 38
로그인해야 코드를 작성할 수 있어요.