6203 : 가중치 변환 최단
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
K개의 간선 가중치를 0으로 만들 수 있을 때, 1번 노드에서 N번 노드까지 가는 최소 가중치 합을 구하시오.
입력 설명
첫째 줄에 노드의 개수 N, 간선의 개수 E, 할인 가능한 간선의 수 K (1 ≤ N, E ≤ 50,000, 1 ≤ K ≤ 10)가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다. (양방향)
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다. (양방향)
출력 설명
K개의 간선 가중치를 0으로 만들었을 때의 최소 가중치 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4 2
1 2 5
1 3 3
2 4 10
3 4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0