문제
Innovative Consumer Products Company (ICPC)는 1급 비밀 프로젝트를 시작할 계획이다.
이 비밀 프로젝트는 s개의 하위 프로젝트로 구성된다.
이 비밀 프로젝트와 연관된 ICPC의 지사들은 b ≥ s 개이며,
ICPC는 각 지사에 하위 프로젝트들 중 하나를 맡기고자 한다.
다시 말해서, 지사들은 s개의 분리된 그룹으로 나누어지고, 각 그룹은 하나의 하위 프로젝트를 맡게 된다.
각 달의 마지막에, 각 지사는 그 그룹에 있는 다른 모든 지사에게 메시지를 보낼 것이다(서로 다른 지사에는 다른 메시지를 보낸다).
ICPC는 통신을 위한 특별한 프로토콜을 가지고 있다. 각 지사 i는 그 지사와 본부에만 공개된 비밀키 ki를 가지고 있다.
지사 i가 지사 j에 메시지를 보내고 싶어한다고 하자. 지사 i는 비밀키 ki로 메시지를 암호화한다.
신뢰할 수 있는 운반원이 이 메시지를 지사로부터 본부까지 전달한다.
본부는 키 ki로 메시지를 복호화하고, 키 kj로 다시 암호화시킨다.
운반원은 새롭게 암호화된 메시지를 (키 kj를 가지고 있는) 지사 j로 전달한다.
보안적인 문제 때문에, 운반원은 동시에 오직 하나의 메시지만 전달할 수 있다.
도로망과 지사와 본부의 위치가 주어졌을 때, 당신은 각 지사에 하위 프로젝트를 배정하는 모든 경우에 대해서,
월말에 운반원이 메시지를 전달하기 위해 이동해야하는 최소 거리를 알아내야 한다.
입력
입력의 첫줄은 4개의 정수 n, b, s, r로 이루어진다.
n (2 ≤ n ≤ 5000)은 교차로의 개수, b (1 ≤ b ≤ n − 1)는 지사의 수, s (1 ≤ s ≤ b)는 하위 프로젝트의 수, r (1 ≤ r ≤ 50,000)은 도로의 수를 나타낸다.
교차로들은 1부터 n까지 숫자가 주어지고, 지사들은 교차로 1부터 교차로 b에 위치하고, 본부는 교차로 b+1에 위치한다.
다음 r개의 줄은 각각 3개의 정수 u, v, l로 이루어진다.
이것은 교차로 u에서 교차로 v로 가는 길이 있고(1 ≤ u, v ≤ n), 이 길이가 l(0 ≤ ℓ ≤ 10,000)임을 뜻한다.
u에서 v로 가는 길은 두번 이상 주어지지 않고, 어느 교차로에서든 다른 모든 교차로로 갈 수 있음이 보장된다.
출력
운반원이 이동해야 할 최소 거리를 출력한다.
예제 #1
5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2
13
예제 #2
5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 10
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2
24
로그인해야 코드를 작성할 수 있어요.