마법 도로
골드 I의견: 0
마법사의 나라에는 \(N\)개의 도시와 \(M\)개의 양방향 도로가 있다. 각 도로에는 이동 비용이 정수로 표시되어 있다.
당신은 도시 \(1\)에서 도시 \(N\)으로 이동하려 한다. 여행에 앞서 마법 업그레이드 를 최대 \(K\)번 사용할 수 있다. 마법 업그레이드를 적용한 도로를 지날 때는 이동 비용이 절반(정수 나누기)으로 줄어든다. 한 도로에는 업그레이드를 최대 한 번만 적용할 수 있다.
도시 \(1\)에서 도시 \(N\)까지의 최소 이동 비용을 구하여라. 경로가 없으면 \(-1\)을 출력한다.
- \(2 \le N \le 100\,000\)
- \(1 \le M \le 200\,000\)
- \(0 \le K \le 10\)
- \(1 \le u, v \le N\), \(\;u \ne v\), \(\;1 \le w \le 10^6\)
첫째 줄에 도시 수 \(N\), 도로 수 \(M\), 마법 업그레이드 횟수 \(K\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 도로 정보 \(u\), \(v\), \(w\)가 공백으로 구분되어 주어진다 (양방향, 비용 \(w\)).
도시 \(1\)에서 도시 \(N\)까지의 최소 이동 비용을 출력한다. 경로가 없으면 \(-1\)을 출력한다.
3 3 1
1 2 10
2 3 2
1 3 100
7
업그레이드 \(1\)회 사용 가능. \(1 \to 2 \to 3\) 경로 비용은 \(10+2=12\)이다. 업그레이드를 \(1 \to 3\)에 쓰면 \(\lfloor 100/2 \rfloor = 50\)으로 더 비싸다. 정답은 \(12\)이다.
4 3 2
1 2 100
2 3 100
3 4 100
200
\(1 \to 2 \to 3 \to 4\)에서 업그레이드 \(2\)개를 앞 두 간선에 쓰면 \(50 + 50 + 100 = 200\)이다. 업그레이드 없이 \(300\)이므로 최적은 \(200\)이다.
riseoj 작성
출처 Original
평가 및 의견
마법 도로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 도로