0110 - Dueling GPS's

USA Compution Olympiad 2014 US OPEN, SILVER

Problem 2: Dueling GPS's

原文 (English)

Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the "Submit" button twice when selecting extra features for the car, and as a result the car ended up equipped with two GPS navigation systems! Even worse, the two systems often make conflicting decisions about the route that FJ should take.

The map of the region in which FJ lives consists of N intersections (2 <= N <= 10,000) and M directional roads (1 <= M <= 50,000). Road i connects intersections A_i (1 <= A_i <= N) and B_i (1 <= B_i <= N). Multiple roads could connect the same pair of intersections, and a bi-directional road (one permitting two-way travel) is represented by two separate directional roads in opposite orientations. FJ's house is located at intersection 1, and his farm is located at intersection N. It is possible to reach the farm from his house by traveling along a series of directional roads.

Both GPS units are using the same underlying map as described above; however, they have different notions for the travel time along each road. Road i takes P_i units of time to traverse according to the first GPS unit, and Q_i units of time to traverse according to the second unit (each travel time is an integer in the range 1..100,000).

FJ wants to travel from his house to the farm. However, each GPS unit complains loudly any time FJ follows a road (say, from intersection X to intersection Y) that the GPS unit believes not to be part of a shortest route from X to the farm (it is even possible that both GPS units can complain, if FJ takes a road that neither unit likes).

Please help FJ determine the minimum possible number of total complaints he can receive if he chooses his route appropriately. If both GPS units complain when FJ follows a road, this counts as +2 towards the total.

和訳 (Japanese)

Farmer John は最近、オンラインで新しい車を購入しましたが、車のオプションを選択するために、彼は急いでいたので誤って 2 回 "送信" をクリックしてしまったので、その結果、車には 2 台の GPSナビが装備されてしまいました！ さらに悪いことに、2 台のシステムは 多くの場合、Farmer John がとるべき経路について、競合する経路を表示します。

Farmer John が住んでいる地域の地図は、N (2 ≦ N ≦ 10,000)個の交差点で構成されていて、M (1 ≦ M ≦ 50,000) 本の道路が存在します。i番目の道路は、交差点 a_i (1 ≦ a_i ≦ N) と b_i (1 ≦ b_i ≦ N) を接続します。これは a_i から b_i に移動できることを意味します。複数の道路が交差点の同じペアを接続することができます。Fermer John は、交差点 1 に位置し、彼の農場は、与えられた道路に沿って移動することによって到達することができる交差点 N に位置しています。

前述したように、2 台の GPSナビは、同じ地図を使用しています。しかしそれらは、それぞれの道路において走行時間は一致しません。道路 i を横断する際の走行時間は、秒単位で記録されていて、一方は P_i、もう一方は Q_i (1 ≦ P_i, Q_i ≦ 100,000, P_i, Q_i は整数) となっています。

Farmer John は、彼の家から農場に移動したいと考えています。しかし、それぞれのGPSナビは、X から農場への最短ルートの一部であると考えていない道を通った(交差点 X から 交差点 Y を通った時)とき、Farmer Johnに毎回苦情を言います(両方のGPSナビが最短ルートでない道を通る場合、両方がFarmer John に苦情を言うことが可能です)。苦情を言ったあとに、そのナビのルートはその位置から再計算されます。

Farmer John は、適切にルートを選択し、彼が受け取るナビからの苦情の数を最小化したいと考えています。この苦情の数を表示して、Farmer John を助けてください。彼が道をたどるとき、両方のGPSナビが苦情を言うならば、合計に +2 としてカウントされます。

入力形式

N M
A1 B1 P1 Q1
A2 B2 P2 Q2
:
AM BM PM QM

1行目に交差点の数 N と 道の数 M が与えられる。
2行目から M 行にかけて、接続される交差点 A_i と B_i, それぞれのナビの走行時間 P_i, Q_i が与えられる。A_iから B_i を、それぞれの GPS において P_i 秒, Q_i 秒で移動できることを意味する(双方向ではない)。

出力形式

1行に、苦情の数の最小値を出力せよ。

入出力例

入力例

5 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 5

出力例

1

解説

Farmer John は、 1 -> 2 -> 4 -> 5 を通る。最初 1台目のGPSが 1 -> 2 に苦情を言う(1 -> 3 が最短ルートの一部となっている)。しかし、 2 -> 4 -> 5 は 両方の GPS にとって最短ルートである。