레이팅 미적용농부 존은 실수로 GPS 내비게이션이 두 대 달린 자동차를 샀는데, 두 GPS는 FJ가 가야 할 경로에 대해 자주 상반된 결정을 내린다.
지도는 N개의 교차로(2 <= N <= 10,000)와 M개의 단방향 도로(1 <= M <= 50,000)로 이루어져 있다. 도로 i는 교차로 A_i와 B_i를 연결한다. 같은 교차로 쌍을 여러 도로가 연결할 수 있으며, 양방향 도로는 두 개의 별도 단방향 도로로 표현된다. FJ의 집은 교차로 1에, 농장은 교차로 N에 있다. 집에서 농장까지는 도달 가능하다.
두 GPS는 같은 지도를 사용하지만 각 도로의 이동 시간에 대한 생각이 다르다: 첫 번째 GPS는 도로 i가 P_i 단위 시간이 걸린다고 보고, 두 번째 GPS는 Q_i 단위라고 본다(각각 1..100,000 범위).
FJ가 어떤 도로(X에서 Y로)를 지날 때, 그 도로가 X에서 농장까지의 최단 경로에 속하지 않는다고 판단하는 GPS는 시끄럽게 불평한다. FJ가 받을 수 있는 총 불평 횟수의 최솟값을 구하는 것을 도와라. 한 도로에서 두 GPS가 모두 불평하면 +2로 센다.
첫째 줄: 정수 N과 M이 주어진다.
둘째 줄부터 1+M째 줄까지: i번째 줄에는 도로 i를 나타내는 네 정수 A_i B_i P_i Q_i가 주어진다.
FJ가 집에서 농장까지 최적으로 경로를 잡을 때 받을 수 있는 총 불평 횟수의 최솟값을 출력한다.
gpsduel.in · 출력을 쓸 파일 gpsduel.out5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 51Output details: Following 1 -> 2 -> 4 -> 5, only the first GPS complains on the 1 -> 2 road.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > US Open > Silver