시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1024 MB | 401 | 61 | 37 | 12.982% |
주의! 이 문제는 NP-hard로 밝혀졌습니다. 하지만 NP-hard 문제를 출제하면 안 된다는 규정이 없었기 때문에 그냥 두기로 했습니다.
정점 n개, 간선 m개로 이루어진 양방향 그래프가 있다. 정점은 1부터 n까지, 간선은 1부터 m까지 번호가 메겨져 있으며 i번 간선의 가중치는 wi이다. (1 ≤ i ≤ m) 이때 자연수 k에 대해서, 1번 정점에서 시작해서 n번 정점에서 끝나는 간선 k개로 이루어진 최단 단순 경로의 길이를 구하여라.
단순 경로란 같은 정점을 두 번 지나지 않는 경로를 의미하며, 경로의 길이는 해당 경로를 구성하는 간선들의 가중치 합을 의미한다.
첫째 줄에 세 정수 n, m, k가 공백으로 구분되어 주어진다.
다음 m개의 줄 중 i번째 줄에는 세 정수 xi, yi, wi가 공백으로 구분되어 주어진다. 이는 i번 간선이 xi번 정점과 yi번 정점을 잇는 가중치 wi의 간선이라는 것을 의미한다.
루프나 다중간선은 주어지지 않는다.
1번 정점에서 시작해서 n번 정점에서 끝나는 간선 k개로 이루어진 최단 단순 경로의 길이를 출력하라. 단, 그러한 경로가 없다면 -1
을 출력하라.
이 서브태스크는 다음의 조건을 만족한다.:
이 서브태스크는 다음의 조건을 만족한다.:
이 서브태스크는 다음의 조건을 만족한다.:
6 6 3 1 2 3 2 3 1 3 6 4 1 4 1 4 5 5 5 6 9
8