Codeforces Round #257 (Div. 2) 質問 D: Jzzhu と Cities 特別なedges_html/css_WEB-ITnose を削除する最短パス

D. Jzzhu と Cities

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Jzzhu はA 国の大統領。彼の国には 1 から n までの番号が付けられた n 個の都市があります。都市 1 は A の首都です。また、都市を結ぶ道路もあります。 i 番目の道路を使用して都市 ui から vi に行くことができます（その逆も同様）。この道路の長さは xi です。最後に、この国には k 個の鉄道路線があります。 i 番目の鉄道ルートを使用して、国の首都からシ市に行くことができます (その逆も同様)。このルートの長さは yi です。

Jzzhu は国のお金を無駄にしたくないので、一部の鉄道路線を運休する予定です。次の条件の下で閉鎖できる鉄道路線の最大数を Jzzhu に伝えてください: すべての都市から首都までの最短経路の長さは変更してはなりません。

入力

最初の行には 3 つの整数が含まれています。 ,?m,?k (2?≤?n?≤?105; 1?≤?m?≤?3·105; 1?≤?k?≤?105)。

次の m 行にはそれぞれ 3 行が含まれますintegers ui,?vi,?xi (1?≤?ui,?vi?≤?n; ui?≠?vi; 1?≤?xi?≤?109).

次の各 k 行には 2 つの整数が含まれますsi and yi (2?≤?si?≤?n; 1?≤?yi?≤?109).

すべての都市から首都まで少なくとも 1 つの道があることが保証されています。 2 つの都市間には複数の道路が存在する可能性があることに注意してください。また、首都から同じ都市に向かう複数のルートが存在する可能性があります。

出力

閉鎖できる鉄道ルートの最大数を表す 1 つの整数を出力します。

サンプル テスト

入力

5 5 31 2 12 3 21 3 33 4 41 5 53 54 55 5

出力

入力

2 2 31 2 22 1 32 12 22 3

出力

思路：これはただ一つの最短路数を入力し、その後再び历火線を通過する、結果最短路火車線の長さと等しく、このとき、最小路数が 1 の場合、この最小路は火車線であることを示し、最小路数が 1 より大きい場合は、この火車線以外にも長さがあることを示します。同様に短い道路でも、廃止することができますが、鉄道の長さが最小の経路よりも長い場合は、廃止することもできます。

は、spfa も、この計算法が手動で実行できることを再認識し、確かに利点が発生しました。デイクストラは優先リストを使用できませんが、これも使用する必要があります。