G - One Step at a Time Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある国には都市 1 から都市 N までの N 個の都市と、道 1 から道 M までの M 本の道があります。
道 i は都市 A_i と都市 B_i を双方向に繋ぎ、C_i 単位時間で通行することができます。
現在都市 1 にいるあなたは Q 日間にわたる旅をします。開始から i 日目の昼には以下のどちらかの行動を行います。

  • 何もしない
  • 今いる都市に繋がっている道を 1 つ選び、その道の先の都市に移動する。このとき選ぶ道は X_i 単位時間以下で通行できるものでなければならない。

1 以上 Q 以下の各整数 i について、開始から i 日目の夕方にあなたがいる可能性のある都市の数を求めてください。
1 単位時間は 1 日の \frac{1}{10^{100}} より短いものとします。

制約

  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le A_i < B_i \le N
  • i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
  • 1 \le C_i \le 10^9
  • 1 \le X_i \le 10^9
  • 入力に含まれる値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M Q
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M
X_1 X_2 X_3 \dots X_Q

出力

Q 行出力せよ。 i 行目には、開始から i 日目の夕方にあなたがいる可能性のある都市の数を出力せよ。

入力例 1

3 3 4
1 2 7
1 3 3
2 3 5
2 4 6 8

出力例 1

1
2
3
3
  • 1 日目
    昼には、都市 1 に繋がっている道で 2 単位時間以下で通れる道はないので、都市 1 にとどまるしかありません。
    夕方にあなたがいる可能性のある都市は、都市 1 の 1 つだけです。
  • 2 日目
    昼には、道 2 のみを使うことができ、都市 3 に移動することができます。都市 1 にとどまることもできます。
    夕方にあなたがいる可能性のある都市は、都市 1, 3 の 2 つです。
  • 3 日目
    昼には、(その道に繋がっている都市にいるならば) 道 2, 3 を使うことができます。前日に都市 3 に移動していれば、この昼に道 3 を使って都市 2 に辿りつけます。
    夕方にあなたがいる可能性のある都市は、都市 1, 2, 3 の 3 つです。
  • 4 日目
    昼には全ての道が使えますが、夕方にあなたがいる可能性のある都市は変わらず都市 1, 2, 3 の 3 つです。

入力例 2

5 7 5
1 2 6
2 3 4
1 3 3
1 4 1
3 4 6
3 5 5
1 5 9
1 5 4 3 5

出力例 2

2
3
4
4
5

1 日に複数本の道を使うことはできないことに注意してください。

入力例 3

4 1 3
1 4 100
50 100 1000000000

出力例 3

1
2
2

道を使って辿り着けない都市が存在するかもしれません。

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In some country, there are N cities called City 1 through City N and M roads called Road 1 through Road N.
Road i connects City A_i and City B_i bidirectionally, and it takes C_i units of time to traverse it.
In City 1, you will start a Q-day trip. On the i-th day, you do one of the following actions:

  • Do nothing.
  • Choose one of the roads that go from the city you are in, and traverse that road to reach the city at the other end. Here, it must take at most X_i units of time to traverse the chosen road.

For each integer i from 1 through Q, find the number of cities that you are potentially in at the i-th night.
Assume that one unit of time is shorter than \frac{1}{10^{100}} days.

Constraints

  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le A_i < B_i \le N
  • (A_i, B_i) \neq (A_j, B_j) for i \neq j
  • 1 \le C_i \le 10^9
  • 1 \le X_i \le 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M Q
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M
X_1 X_2 X_3 \dots X_Q

Output

Print Q lines. The i-th line should contain the number of cities that you are potentially in at the i-th night.

Sample Input 1

3 3 4
1 2 7
1 3 3
2 3 5
2 4 6 8

Sample Output 1

1
2
3
3
  • Day 1:
    There are no roads that go from City 1 and take at most 2 units of time to traverse, so you have to stay there.
    There is just one city that you are potentially in at night: City 1.
  • Day 2:
    Only Road 2 is available, which takes you to City 3. You can also choose to stay at City 1.
    There are two cities that you are potentially in at night: City 1 and 3.
  • Day 3:
    Roads 2 and 3 are available (if you are in a city they go from). If you moved to City 3 the previous day, you can use Road 3 to reach City 2 this day.
    There are three cities that you are potentially in at night: City 1, 2, and 3.
  • Day 4:
    All roads are available, but there are still three cities that you are potentially in at night: City 1, 2, and 3.

Sample Input 2

5 7 5
1 2 6
2 3 4
1 3 3
1 4 1
3 4 6
3 5 5
1 5 9
1 5 4 3 5

Sample Output 2

2
3
4
4
5

Note that you cannot traverse multiple roads in a day.

Sample Input 3

4 1 3
1 4 100
50 100 1000000000

Sample Output 3

1
2
2

There may be cities unreachable by roads.