환승 제한 여행
골드 II의견: 0
여행자 소희는 도시 \(1\)에서 도시 \(N\)으로 가려 한다. \(M\)개의 단방향 항공편이 있고, 각 항공편에는 비용 \(w\)가 있다 (\(w < 0\)이면 마일리지 환급). 음수 사이클은 없다.
소희는 최대 \(K\)번의 환승(간선 사용)만 허용되는 티켓을 갖고 있다. 이 조건 아래 도시 \(1\)에서 도시 \(N\)까지의 최솟값 비용을 구하여라.
도달할 수 없으면 \(-1\)을 출력한다.
- \(2 \le N \le 500\)
- \(0 \le M \le 5\,000\)
- \(1 \le K \le N-1\)
- \(-10^6 \le w \le 10^6\)
- 음수 사이클은 없다.
첫째 줄에 도시의 수 \(N\), 항공편의 수 \(M\), 최대 환승 횟수 \(K\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 항공편 \(u\), \(v\), \(w\)가 주어진다 (\(u\)에서 \(v\)로 비용 \(w\)인 편도 항공편).
최대 \(K\)개의 간선을 사용한 \(1 \to N\) 최솟값 비용을 출력한다. 도달할 수 없으면 \(-1\)을 출력한다.
4 5 2
1 2 2
1 3 5
2 4 3
3 4 1
1 4 10
5
간선을 최대 \(2\)개 쓸 수 있다. \(1\to2\to4 = 2+3=5\), \(1\to3\to4 = 5+1=6\), \(1\to4=10\) 중 가장 짧은 \(5\)가 답이다.
4 4 2
1 2 4
2 3 -2
3 4 3
1 4 20
20
\(k=2\)이므로 간선 최대 \(2\)개. \(1\to4=20\), \(1\to2\)(이후 더 가면 \(3\)개 필요)로 \(4\)에 직접 도달 불가. 최선은 \(20\)이다.
riseoj 작성
출처 Original
평가 및 의견
환승 제한 여행
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
환승 제한 여행