AT_abc235_h [ABC235Ex] Painting Weighted Graph

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的无向图。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，权值为 $C_i$。

最初，所有顶点都被涂成黑色。你最多可以进行 $K$ 次如下操作：

• 操作：任选一个顶点 $v$ 和一个整数 $x$。将从顶点 $v$ 出发，只经过权值不超过 $x$ 的边能够到达的所有顶点（包括 $v$ 本身）涂成红色。

问经过操作后，可能作为红色顶点集合的不同方案有多少种？请输出方案数对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$ $K$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 2 1
1 2 1
2 3 2

输出 #1

6

输入输出样例 #2

输入 #2

5 0 2

输出 #2

16

输入输出样例 #3

输入 #3

6 8 2
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 1 3
1 2 10
1 1 100

输出 #3

40

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq K \leq 500$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 输入中的所有数均为整数

样例解释 1

例如，选择 $(v, x) = (2, 1)$ 进行操作时，可以将顶点 $1, 2$ 涂成红色；选择 $(v, x) = (1, 0)$ 进行操作时，可以将顶点 $1$ 涂成红色。最多进行 $1$ 次操作后，可能的红色顶点集合有 $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,2,3\}$ 共 $6$ 种。

样例解释 2

给定的图不一定是连通的。

样例解释 3

给定的图可能包含重边或自环。

由 ChatGPT 4.1 翻译