P10525 [XJTUPC 2024] Operations on a Graph

You are given a **directed graph** with $n$ vertices and $m$ edges, where the vertices are numbered from $1$ to $n$. Each edge has a positive integer weight $d_i$. In particular, $1\le d_i \le 100$. Now define the bottleneck path value of vertex $i$ as follows: among all directed paths from vertex $1$ to vertex $i$, take the minimum edge weight on each path, and then take the maximum of these minimum values. In particular, if $i$ is not reachable from $1$, then its bottleneck path value is $0$. There are $q$ modifications. Each modification specifies an edge and decreases its weight, and it is guaranteed that the weight is still a positive integer after the decrease. After each modification, output the bottleneck path values of vertices $2\sim n$. Note that each modification is applied on top of all previous modifications; they are not independent. Since the output is too large, let the bottleneck path value of vertex $i$ after a modification be $ans_i$. You only need to output $(\sum_{i=2}^n ans_i \times 2^i)\bmod 998244353$ after each modification.

The first line contains three positive integers $n,m,q$ ($2\le n\le 1\times 10^5$，$1\le m \le 2\times 10^5$，$1\le q\le 2\times 10^5$), separated by spaces, with the meanings as described above. The next $m$ lines each contain three positive integers $s_i,t_i,d_i$ ($1\le s_i,t_i\le n$，$s_i\neq t_i$，$1\le d_i \le 100$), separated by spaces, indicating that there is a directed edge from $s_i$ to $t_i$ with weight $d_i$. The index of this edge is $i$. It is guaranteed that there are no self-loops, but there may be multiple edges. The next $q$ lines each contain two positive integers $x,y$ ($1\le x\le m$，$1\le y < d_x$), separated by spaces, indicating that the weight of edge $x$ is decreased by $y$, and it is guaranteed that the resulting weight is greater than $0$.

Output $q$ lines, each containing one non-negative integer, which is the answer you computed.

After the first modification, the bottleneck path value of vertex $2$ is $3$, and the bottleneck path value of vertex $3$ is $4$. After the second modification, the bottleneck path value of vertex $2$ is $3$, and the bottleneck path value of vertex $3$ is $3$. After the third modification, the bottleneck path value of vertex $2$ is $1$, and the bottleneck path value of vertex $3$ is $2$. After the fourth modification, the bottleneck path value of vertex $2$ is $1$, and the bottleneck path value of vertex $3$ is $2$. Translated by ChatGPT 5