C - 鉄道運賃 (Train Fare) (original) (raw)
C - 鉄道運賃 (Train Fare)Editorial 
/ 
Time Limit: 2.5 sec / Memory Limit: 256 MB
配点： 100 点
JOI 国には N 個の都市があり，それぞれ 1, 2, \ldots, N の番号が付けられている．都市 1 は JOI 国の首都である．
また，JOI 国には鉄道会社がひとつだけあり，この会社は M 個の路線を運行している．これらの路線にはそれぞれ 1, 2, \ldots, M の番号が付けられており，i 番目 (1 \leqq i \leqq M) の路線は都市 U_i と都市 V_i を双方向に結んでいる．都市と都市の間を鉄道以外で移動することはできない．また，どの都市からどの都市へもいくつかの路線を乗り継いで移動することができるようになっている．
現在，どの路線の運賃も 1 円である．経営不振に陥った鉄道会社は，今後 Q 年間かけていくつかの路線の運賃を値上げする計画を立てた．この計画では，計画開始から j 年目 (1 \leqq j \leqq Q) の年初めに路線 R_j の運賃を 1 円から 2 円に値上げする予定である．値上げされた路線の運賃は，その後ずっと 2 円のままであり，再び値上げすることはない．
ところで，この鉄道会社では，毎年，各都市の住民の満足度調査を行っている．計画開始前は，どの都市の住民もこの鉄道会社に満足しているが，値上げによって不満を持つ住民が現れる可能性がある．
それぞれの年の満足度調査は，その年の値上げの実施後に行う．したがって，j 年目 (1 \leqq j \leqq Q) の満足度調査は，路線 R_1, R_2, \ldots, R_j の運賃の値上げは完了し，それ以外の路線の運賃は値上げされていない状態で行われることになる．j 年目 (1 \leqq j \leqq Q) の満足度調査では，都市 k (2 \leqq k \leqq N) の住民は，以下の条件が満たされるとき，そしてそのときに限り鉄道会社に不満を抱く．
- その時の運賃で都市 k から首都である都市 1 へ移動するときの費用の最小値が，計画開始前の運賃で都市 k から都市 1 へ移動するときの費用の最小値よりも大きい．
ただし，いくつかの路線を使って移動するときの費用は，それぞれの路線の運賃の合計である．また，都市 1 の住民が鉄道会社に対して不満を抱くことはない．値上げ後の運賃で最小の費用を達成する経路は，計画開始前の運賃で最小の費用を達成する経路と異なる可能性があることに注意せよ．
計画の実行に先立って，今後 Q 年間の住民の満足度調査それぞれにおいて，鉄道会社に不満を抱く住民がいる都市の数を計算しておきたい．
課題
JOI 国の鉄道路線の情報と，運賃の値上げ計画が与えられたとき，それぞれの満足度調査において鉄道会社に不満を抱く住民がいる都市の数を求めるプログラムを作成せよ．
入力
標準入力から以下の入力を読み込め．
- 1 行目には，3 個の整数 N, M, Q が空白を区切りとして書かれている．これらは，JOI 国には N 個の都市と M 個の路線があり，運賃の値上げ計画が Q 年間に渡ることを表している．
- 続く M 行のうちの i 行目 (1 \leqq i \leqq M) には，2 個の整数 U_i, V_i が空白を区切りとして書かれている．これらは，i 番目の路線が都市 U_i と都市 V_i を結んでいることを表している．
- 続く Q 行のうちの j 行目 (1 \leqq j \leqq Q) には，整数 R_j が書かれている．これは，計画の j 年目に路線 R_j の運賃を値上げすることを表している．
出力
標準出力に Q 行で出力せよ．j 行目 (1 \leqq j \leqq Q) には，j 年目の満足度調査で不満を抱く住民がいる都市の数を出力せよ．
制限
すべての入力データは以下の条件を満たす．
- 2 \leqq N \leqq 100\,000．
- 1 \leqq Q \leqq M \leqq 200\,000．
- 1 \leqq U_i \leqq N (1 \leqq i \leqq M)．
- 1 \leqq V_i \leqq N (1 \leqq i \leqq M)．
- U_i \neq V_i (1 \leqq i \leqq M)．
- 1 \leqq R_j \leqq M (1 \leqq j \leqq Q)．
- R_j \neq R_k (1 \leqq j < k \leqq Q)．
- どの 2 つの都市についても，それらを直接結ぶ路線は 1 個以下である．
- どの都市についても，その都市から都市 1 までいくつかの路線を使って移動することができる．
小課題
小課題 1 [12 点]
以下の条件を満たす．
- N \leqq 100．
- M \leqq 4\,950．
- Q \leqq 30．
小課題 2 [14 点]
- Q \leqq 30 を満たす．
小課題 3 [35 点]
- 正しい出力に現れる整数は 50 種類以下である．
小課題 4 [39 点]
追加の制限はない．
入力例 1
5 6 5 1 2 1 3 4 2 3 2 2 5 5 3 5 2 4 1 3
出力例 1
0 2 2 4 4
この入力例では，計画開始前，及びそれぞれの満足度調査の時点でのそれぞれの都市から都市 1 への運賃は，以下の表のようになる．
例えば，3 年目の満足度調査では，都市 3 と都市 5 の住民が不満を抱くので，出力の 3 行目には 2 を出力する．
入力例 2
4 6 6 1 2 1 3 1 4 2 3 2 4 3 4 1 4 2 5 3 6