102357: [AtCoder]ABC235 Ex - Painting Weighted Graph
Description
Score : $600$ points
Problem Statement
Given is an undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects Vertices $A_i$ and $B_i$ and has a weight of $C_i$.
Initially, all vertices are painted black. You can do the following operation at most $K$ times.
- Operation: choose any vertex $v$ and any integer $x$. Paint red all vertices reachable from the vertex $v$ by traversing edges whose weights are at most $x$, including $v$ itself.
How many sets can be the set of vertices painted red after the operations?
Find the count modulo $998244353$.
Constraints
- $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $K$ $A_1$ $B_1$ $C_1$ $\vdots$ $A_M$ $B_M$ $C_M$
Output
Print the answer.
Sample Input 1
3 2 1 1 2 1 2 3 2
Sample Output 1
6
For example, an operation with $(v,x)=(2,1)$ paints Vertices $1,2$ red, and an operation with $(v,x)=(1,0)$ paints Vertex $1$.
After at most one operation, the set of vertices painted red can be one of the following six: $\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$.
Sample Input 2
5 0 2
Sample Output 2
16
The given graph may not be connected.
Sample Input 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
Sample Output 3
40
The given graph may have multi-edges and self-loops.
Input
题意翻译
给定一个 $n$ 个点 $m$ 条边的无向带权图，初始时点全为黑色。 你可以在这张图上进行**不超过 $k$ 次**操作，每次操作可被描述为如下形式： 1. 选择一个点 $u$ 和一个整数 $x$。 2. 将所有从点 $u$ 出发，**只经过边权不大于 $x$ 的边** 能到达的所有点 $v$ 染红。 设所有被染红的点构成的点集为 $S$，求**不超过 $k$ 次**操作后能构成多少个不同的 $S$。答案对 $998244353$ 取模。 两个集合 $S_1,S_2$ 被视为不同当且仅当存在一个元素 $e$，其只属于 $S_1,S_2$ 中的一个。Output
分数：600分
问题描述
给定一个有N个顶点和M条边的无向图。第i条边连接顶点A_i和B_i，权重为C_i。
最初，所有顶点都被涂成黑色。你可以最多执行K次以下操作。
- 操作：选择任意一个顶点v和任意一个整数x。将从顶点v出发，通过权重不超过x的边可以到达的所有顶点（包括v本身）涂成红色。
操作结束后，可以被涂成红色的顶点集合有多少种可能？
找出结果对998244353取模后的值。
限制条件
- 2≤N≤10^5
- 0≤M≤10^5
- 1≤K≤500
- 1≤A_i,B_i≤N
- 1≤C_i≤10^9
- 输入中的所有值都是整数。
输入
从标准输入按以下格式给出输入：
$N$ $M$ $K$ $A_1$ $B_1$ $C_1$ $\vdots$ $A_M$ $B_M$ $C_M$
输出
打印答案。
样例输入1
3 2 1 1 2 1 2 3 2
样例输出1
6
例如，一次操作（v,x）=（2,1）将顶点1,2涂成红色，一次操作（v,x）=（1,0）将顶点1涂成红色。
在最多执行一次操作后，被涂成红色的顶点集合可能是以下六种之一：$\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$。
样例输入2
5 0 2
样例输出2
16
给定的图可能不连通。
样例输入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
给定的图可能包含多边和自环。