Dueling GPS's
실버 II의견: 0
Farmer John accidentally bought a car equipped with two GPS navigation systems, which often make conflicting decisions about the route FJ should take.
The map consists of N intersections (2 <= N <= 10,000) and M directional roads (1 <= M <= 50,000). Road i connects intersections A_i and B_i. Multiple roads could connect the same pair of intersections, and a bi-directional road is represented by two separate directional roads. FJ's house is at intersection 1, and his farm is at intersection N. It is possible to reach the farm from his house.
Both GPS units use the same map, but have different notions for the travel time along each road: road i takes P_i units of time according to the first GPS unit, and Q_i units according to the second (each in the range 1..100,000).
Each GPS unit complains loudly any time FJ follows a road (from X to Y) that the GPS unit believes not to be part of a shortest route from X to the farm. Please help FJ determine the minimum possible number of total complaints he can receive. If both GPS units complain on a road, this counts as +2.
Line 1: The integers N and M.
Lines 2..1+M: Line i describes road i with four integers: A_i B_i P_i Q_i.
The minimum total number of complaints FJ can receive if he routes himself from his house to the farm optimally.
gpsduel.ingpsduel.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
평가 및 의견
Dueling GPS's
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Dueling GPS's