MCC 2025 P5: Reachability Queries

Reachability Queries

Statement

The Magical Charming Conurbation (MCC) is an area consisting of $N$ cities numbered $1, 2, \ldots, N$. There are $M$ two-way roads numbered $1, 2, \ldots, M$. Each road connects two different cities and has a length. $S$ of the roads are damaged.

Initially, Evirir the dragon is in city $1$. If Evirir is in city $x$ and there is a road between cities $x$ and $y$ with length $w$, then it can go to city $y$ in $w$ minutes. Roads can be travelled in both ways. This is the only way Evirir can go to other cities.

As a divine dragon, Evirir senses that there will be an apocalypse $K$ minutes from now, which will break all damaged roads. This means:

• Evirir cannot travel on damaged roads starting $K$ minutes from now (including at exactly $K$ minutes).
• Evirir also cannot travel on a damaged road if the apocalypse will happen while it is on the road. If Evirir will finish travelling a road at exactly $K$ minutes, it can do so.

A city $x$ is reachable if Evirir can reach city $x$ by travelling on roads while being safe from the apocalypse. Note that city $1$ is always reachable. Also, Evirir can travel as long as it wants, even after the apocalypse.

Now, Evirir isn’t sure about the value of $K$. It has $Q$ possible values of $K$ (each value is a query), and for each of them, it wants to know: how many cities are reachable?

Input Format

The first line contains two space-separated integers, $N$ and $M$.

The $i$-th of the next $M$ lines contains three space-separated integers $x$, $y$, and $w$, meaning road $i$ connects city $x$ and $y$ and has length $w$. For every pair of cities, there is at most one road connecting them.

The next line contains an integer $S$, the number of damaged roads.

The next line contains $S$ space-separated integers $d_1, d_2, \ldots, d_S$, meaning roads $d_1, d_2, \ldots, d_S$ are damaged. This will be an empty line if $S = 0$.

The next line contains the number of queries $Q$.

The next $Q$ lines each contains a single integer $K$.

Output Format

Output $Q$ lines, the $i$-th of which contains an integer, the answer to the $i$-th query in the input.

Constraints

For all tasks:

• $1 \le N, M \le 3 \cdot 10^5$.
• $1 \le x, y \le N$, $x \ne y$.
• $1 \le w \le 10^{5}$.
• $0 \le S \le N$.
• $1 \le Q \le 10^5$.

• $0 \le K \le 10^{9}$.

• Group 1: $S = 0$ (no road is damaged), $N, M \le 100$, $Q \le 10$, $w \le 1000$, $K \le {10}^{5}$
• Group 2: $N, M \le 5000$, $Q \le 5000$

• Group 3: No additional constraints.

• Task 1 (10 points): Group 1, $w = 1$ for all roads
• Task 2 (10 points): Group 1
• Task 3 (10 points): Group 2, $w = 1$ for all roads
• Task 4 (10 points): Group 2, $w = 1$ for all roads
• Task 5 (10 points): Group 2
• Task 6 (10 points): Group 2
• Task 7 (10 points): Group 3, $w = 1$ for all roads
• Task 8 (10 points): Group 3, $w = 1$ for all roads
• Task 9 (10 points): Group 3
• Task 10 (10 points): Group 3

Sample Input

5 6
1 2 7
2 3 10
4 3 8
4 2 5
1 5 18
3 5 20
4
1 3 4 6
3
6
11
12

Sample Output

2
4
5

Sample Explanation

The damaged roads are road $1$ (between cities 1 and 2), road $3$ (between cities 4 and 3), road $4$ (between cities 4 and 2), and road $6$ (between cities 3 and cities 5).

For the first query, the apocalypse is $K = 6$ minutes from now. Evirir cannot reach any city other than city 1 before the apocalypse, as no road from city $1$ has a length of $6$ or less. After the apocalypse, Evirir can reach $2$ cities: cities $1$ and $5$ as shown in Figure 1.

For the second query, the apocalypse is $K = 11$ minutes from now. Evirir can reach all the cities except city 4. Evirir cannot reach city 4 before the apocalypse happens (i.e. there is no sequence of connecting roads that will reach city 4 by $K = 11$ minutes: the fastest way to reach city 4 is through the road from city 1 to city 2, then through the road from city 2 to city 4, which in total takes 12 minutes). After the apocalypse, all roads connecting city 4 are destroyed. Hence, there is no way Evirir can reach city 4. Evirir can reach all other cities as described in Figure 2.

For the third query, the apocalypse is $K = 12$ minutes from now. Evirir can reach all the cities. Now, Evirir can reach city 4 before the apocalypse happens by travelling from city 1 to city 2, then to city 4. Evirir can still reach all other cities as described in Figure 2 too.

In the figures below, a circle numbered $x$ represents city $x$, and a line segment labelled $w$ between two circles represents the road connecting the two cities with length $w$.

Figure 1: Showing cities reachable by the dragon for query 1 with $K=6$.


Figure 2: Showing cities reachable by the dragon for query 2 with $K=11$.

Pertanyaan Kebolehcapaian (Reachability Queries)

Pernyataan

Magical Charming Conurbation (MCC) ialah sebuah kawasan yang terdiri daripada $N$ bandar bernombor $1, 2, \ldots, N$. Terdapat $M$ jalan dua hala bernombor $1, 2, \ldots, M$. Setiap jalan menghubungkan dua bandar yang berbeza dan mempunyai panjang. Sebanyak $S$ daripada jalan-jalan ini adalah rosak.

Pada mulanya, Evirir si naga berada di bandar $1$. Jika Evirir berada di bandar $x$ dan terdapat jalan antara bandar $x$ dan $y$ dengan panjang $w$, maka Evirir boleh pergi ke bandar y dalam masa $w$ minit. Jalan boleh dilalui dua hala. Ini ialah satu-satunya cara Evirir boleh bergerak ke bandar lain.

Sebagai naga sakti, Evirir merasakan bahawa malapetaka akan berlaku dalam $K$ minit dari sekarang, yang akan memutuskan semua jalan yang rosak. Ini bermaksud:

• Evirir tidak boleh menggunakan jalan yang rosak bermula pada masa $K$ minit dari sekarang (termasuk tepat pada $K$ minit).
• Evirir juga tidak boleh menggunakan jalan rosak jika malapetaka akan berlaku semasa Evirir sedang berada di atas jalan tersebut. Jika Evirir menamatkan perjalanan di atas sesuatu jalan tepat pada $K$ minit, itu masih dibenarkan.

Sebuah bandar $x$ dikatakan boleh dicapai (reachable) jika Evirir boleh sampai ke bandar $x$ dengan melalui jalan-jalan sambil kekal selamat daripada malapetaka. Perhatikan bahawa bandar 1 sentiasa boleh dicapai. Selain itu, Evirir boleh terus bermusafir selama mana yang dikehendaki, walaupun selepas malapetaka.

Kini, Evirir tidak pasti tentang nilai $K$. Evirir mempunyai $Q$ kemungkinan nilai $K$ (setiap satunya dipanggil pertanyaan), dan bagi setiap nilai tersebut Evirir ingin tahu: berapa banyak bandar yang boleh dicapai?

Format Input

Baris pertama mengandungi dua integer yang dipisahkan oleh ruang, $N$ dan $M$.

Baris ke-$i$ daripada $M$ baris seterusnya mengandungi tiga integer dipisahkan oleh ruang, $x$, $y$, dan $w$, yang bermaksud jalan ke-$i$ menghubungkan bandar $x$ dan $y$ dengan panjang $w$. Bagi setiap pasangan bandar, paling banyak satu jalan menghubungkan mereka.

Baris seterusnya mengandungi integer $S$, bilangan jalan yang rosak.

Baris seterusnya mengandungi $S$ integer dipisahkan oleh ruang, $d_1, d_2, \ldots, d_S$, yang bermaksud jalan bernombor $d_1, d_2, \ldots, d_S$ adalah rosak. Baris ini kosong jika $S = 0$.

Baris seterusnya mengandungi bilangan pertanyaan $Q$.

Setiap satu daripada $Q$ baris berikutnya mengandungi satu integer $K$.

Format Output

Keluarkan Q baris; baris ke-$i$ mengandungi satu integer, iaitu jawapan bagi pertanyaan ke-$i$ dalam input.

Kekangan

Untuk semua tugasan:

• $1 \le N, M \le 3 \cdot 10^5$.
• $1 \le x, y \le N$, $x \ne y$.
• $1 \le w \le 10^{5}$.
• $0 \le S \le N$.
• $1 \le Q \le 10^5$.

• $0 \le K \le 10^{9}$.

• Kumpulan 1: $S = 0$ (tiada jalan rosak), $N, M \le 100$, $Q \le 10$, $w \le 1000$, $K \le 10^5$
• Kumpulan 2: $N, M \le 5000$, $Q \le 5000$

• Kumpulan 3: Tiada kekangan tambahan.

• Tugasan 1 (10 markah): Kumpulan 1, $w = 1$ untuk semua jalan
• Tugasan 2 (10 markah): Kumpulan 1
• Tugasan 3 (10 markah): Kumpulan 2, $w = 1$ untuk semua jalan
• Tugasan 4 (10 markah): Kumpulan 2, $w = 1$ untuk semua jalan
• Tugasan 5 (10 markah): Kumpulan 2
• Tugasan 6 (10 markah): Kumpulan 2
• Tugasan 7 (10 markah): Kumpulan 3, $w = 1$ untuk semua jalan
• Tugasan 8 (10 markah): Kumpulan 3, $w = 1$ untuk semua jalan
• Tugasan 9 (10 markah): Kumpulan 3
• Tugasan 10 (10 markah): Kumpulan 3

Contoh Input

5 6
1 2 7
2 3 10
4 3 8
4 2 5
1 5 18
3 5 20
4
1 3 4 6
3
6
11
12

Contoh Output

2
4
5

Penjelasan Contoh

Jalan yang rosak ialah jalan $1$ (antara bandar 1 dan 2), jalan $3$ (antara bandar 4 dan 3), jalan $4$ (antara bandar 4 dan 2) dan jalan $6$ (antara bandar 3 dan 5).

Bagi pertanyaan pertama, malapetaka berlaku pada $K = 6$ minit dari sekarang. Evirir tidak boleh mencapai mana-mana bandar selain bandar 1 sebelum malapetaka, kerana tiada jalan dari bandar $1$ yang panjangnya $6$ atau kurang. Selepas malapetaka, Evirir boleh mencapai $2$ bandar: bandar $1$ dan $5$ (lihat Rajah 1).

Bagi pertanyaan kedua, $K = 11$ minit. Evirir boleh mencapai semua bandar kecuali bandar 4. Evirir tidak sempat ke bandar 4 sebelum malapetaka berlaku (tiada rangkaian jalan yang sampai ke bandar 4 dalam masa $K = 11$ minit; cara terpantas untuk sampai ke bandar 4 ialah melalui jalan daripada bandar 1 ke bandar 2, kemudian melalui jalan antara bandar 2 dan bandar 4, iaitu jumlahnya ialah 12 minit). Selepas malapetaka, semua jalan yang menghubungkan bandar 4 telah musnah. Maka, tiada cara untuk sampai ke bandar 4. Evirir boleh mencapai semua bandar lain seperti dalam Rajah 2.

Bagi pertanyaan ketiga, malapetaka ialah $K = 12$ minit dari sekarang. Evirir boleh mencapai semua bandar. Kini Evirir sempat ke bandar 4 sebelum malapetaka dengan melalui jalan daripada bandar 1 ke bandar 2, kemudian ke bandar 4. Bandar-bandar lain masih boleh dicapai seperti dalam Rajah 2.

Dalam rajah, bulatan bernombor $x$ mewakili bandar $x$, dan segmen garisan berlabel $w$ antara dua bulatan mewakili jalan antara dua bandar dengan panjang $w$.

Rajah 1: Menunjukkan bandar-bandar yang boleh dicapai oleh naga itu untuk pertanyaan 1 dengan $K=6$.


Rajah 2: Menunjukkan bandar-bandar yang boleh dicapai oleh naga tersebut untuk pertanyaan 2 dengan $K=11$.

可达性查询

题目描述

Magical Charming Conurbation (MCC) 是一个地区，包含了 $N$ 座编号为 $1, 2, \ldots, N$ 的城市。除此之外，也有 $M$ 条双向路，编号为 $1, 2, \ldots, M$。 每条路都有一个长度且连接了两座不一样的城市。其中 $S$ 条路是损坏的。

起初，Evirir 龙在城市 $1$。如果 Evirir 在城市 $x$ 且有一条长度为 $w$ 的路连接城市 $x$ 和 $y$，那么它可以用 $w$ 分钟前往城市 $y$。这条路是双向的。这是 Evirir 去往其他城市的唯一方法。

身为一条神圣的龙，Evirir 可以感知到 $K$ 分钟后将会有一场末日灾难。这个灾难会完全破坏所有损坏的路。也就是说：

• Evirir 在 $K$ 分钟后（包括在 $K$ 分钟时）不能使用损坏的路。
• Evirir 也不能使用损坏的路如果灾难发生时，它还在路上。如果 Evirir 在 $K$ 分钟时，抵达城市，那么它可以使用该损坏的路。

一座城市 $x$ 是可达的如果 Evirir 可以通过路安全地抵达城市 $x$。城市 $1$ 是可达的。另外，Evirir 可以随意走动即使是在灾难之后。

其实 Evirir 不是非常确定 $K$ 的值。它有 $Q$ 个可能的 $K$（每一个值被称为一个查询）。对于每一个值，它想知道有多少个城市是可达的。

输入格式

第一行包含两个整数 - $N$ 和 $M$。

接下来的 $M$ 行中，第 $i$ 行包含三个用空格分隔的整数 $x$、$y$ 和 $w$，表示第 $i$ 条道路连接城市 $x$ 和城市 $y$，长度为 $w$。任意一对城市之间最多只有一条道路相连。

接下来一行包含一个整数 $S$，表示受损道路的数量。

下一行包含 $S$ 个用空格分隔的整数 $d_1, d_2, \ldots, d_S$，表示编号为 $d_1, d_2, \ldots, d_S$ 的道路受损。若 $S = 0$，则这一行为空行。

再接下来一行包含一个整数 $Q$，表示查询的数量。

接下来的 $Q$ 行中，每一行包含一个整数 $K$。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，对于第 $i$ 个查询的答案。

约束

对于每项任务：

• $1 \le N, M \le 3 \cdot 10^5$。
• $1 \le x, y \le N$, $x \ne y$。
• $1 \le w \le 10^{5}$。
• $0 \le S \le N$。
• $1 \le Q \le 10^5$。

• $0 \le K \le 10^{9}$。

• 组 1: $S = 0$（没有一条路是损坏的）, $N, M \le 100$, $Q \le 10$, $w \le 1000$, $K \le {10}^{5}$
• 组 2: $N, M \le 5000$, $Q \le 5000$

• 组 3: 无额外约束

• 任务 1（10 分）：组 1，对于每条路 $w = 1$
• 任务 2（10 分）：组 1
• 任务 3（10 分）：组 2，对于每条路 $w = 1$
• 任务 4（10 分）：组 2，对于每条路 $w = 1$
• 任务 5（10 分）：组 2
• 任务 6（10 分）：组 2
• 任务 7（10 分）：组 3，对于每条路 $w = 1$
• 任务 8（10 分）：组 3，对于每条路 $w = 1$
• 任务 9（10 分）：组 3
• 任务 10（10 分）：组 3

样例输入

5 6
1 2 7
2 3 10
4 3 8
4 2 5
1 5 18
3 5 20
4
1 3 4 6
3
6
11
12

样例输出

2
4
5

样例解释

损坏的路是 第$1$个路（连接城市1和2）， 第$3$个路（连接城市4和3），第$4$个路（连接城市4和2）和第$6$个路（连接城市3和5）。

对于第一个查询，灾难在 $K = 6$ 分钟发生。灾难发生前，Evirir 无法抵达除了城市1之外的任意城市因为没有一条连接城市 $1$ 且长度少于等于 $6$。灾难发生后，Evirir 可以抵达两座城市：城市 $1$ 和 $5$ 如图一所示。

对于第二个查询，灾难在 $K = 11$ 分钟发生。Evirir 可以抵达除了城市4之外的所有城市。灾难发生前，Evirir 无法抵达城市4（即不存在一条在 $K=11$ 分钟内到达城市 4 的连通道路序列：到达城市 4 的最快路径是先经过城市 1 到城市 2 的道路，然后再经过城市 2 到城市 4 的道路，总共需要 12 分钟。） 灾难发生后，所有与城市 4 连接的路都被摧毁了。所以，不管怎样 Evirir 都无法抵达城市 4。Evirir 可以抵达其他城市如图二所示。

对于第三个查询，灾难在 $K = 12$ 分钟发生。Evirir 可以抵达所有城市。现在，Evirir 可以在灾难发生前从城市 1 到 城市 2，然后再到城市 4。Evirir 也可以到达其他的城市如图二所示。

在下图中，编号为 $x$ 的圆表示城市 $x$，而连接两个圆并标有 $w$ 的线段表示这两座城市之间长度为 $w$ 的道路。

图一：展示在查询 1 （即 $K = 6$）的情况下可以到达的城市。


图二：展示在查询 2 （即 $K = 11$）的情况下可以到达的城市。