환승 제한 지하철
골드 IV의견: 0
지하철 노선망에서 한 승객이 역 \(s\) 에서 역 \(e\) 까지 이동하려고 한다. 두 역을 잇는 구간마다 요금이 정해져 있다. 그런데 이 승객은 환승을 너무 많이 하기 싫어서 중간에 들르는 역(경유역)의 수를 최대 \(K\) 개로 제한하려고 한다.
즉, 출발역 \(s\) 와 도착역 \(e\) 를 제외하고 거쳐가는 역의 수가 \(K\) 개를 넘지 않아야 한다 (지나는 구간 수는 최대 \(K+1\) 개). 이 조건을 지키면서 \(s\) 에서 \(e\) 까지 이동하는 최소 요금을 구하여라.
구간은 한 방향으로만 이동할 수 있다. 조건을 만족하며 도달할 수 없으면 \(-1\) 을 출력한다.
\(2 \le n \le 12{,}000\), \(1 \le m \le 36{,}000\), \(0 \le K \le 25\)
첫째 줄에 역의 수 \(n\) 과 구간의 수 \(m\) 이 주어진다. (\(2 \le n \le 12{,}000\), \(1 \le m \le 36{,}000\))
다음 \(m\) 개의 줄에 세 정수 \(u\ v\ w\) 가 주어지며, 역 \(u\) 에서 역 \(v\) 로 가는 요금 \(w\) 의 단방향 구간을 의미한다. (\(1 \le u, v \le n\), \(u \ne v\), \(1 \le w \le 10{,}000\))
마지막 줄에 출발역 \(s\), 도착역 \(e\), 경유역 제한 \(K\) 가 주어진다. (\(0 \le K \le 25\))
최소 요금을 출력한다. 조건을 만족하며 도달할 수 없으면 \(-1\) 을 출력한다.
4 5
1 2 100
2 4 100
1 3 50
3 2 50
3 4 500
1 4 1200\(K=1\) 이므로 경유역은 최대 1개. \(1\to2\to4\) (요금 200, 경유역 1개) 가 최적이다. \(1\to3\to2\to4\) 는 경유역 2개라 불가.
3 2
1 2 5
2 3 5
1 3 0-1\(K=0\) 이라 경유역이 없어야 하는데, \(1\to3\) 직행 구간이 없으므로 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
환승 제한 지하철
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
환승 제한 지하철