Limits
5s, 512 MB

One fine morning you discovered yourself standing in a maze. The maze can be considered a **connected weighted undirected** graph. You are currently standing in vertex $s$ and to get out of the maze you need to go to vertex $t$. But there’s a catch. In order to get out of the maze you need to choose a path from $s$ to $t$ such that, the path length differs from the shortest path length of $s$ to $t$ by at-most $k$. You are wondering how many ways are there to solve the maze.

More formally, count the number of paths from $s$ to $t$ in a connected weighted undirected graph such that, the path length differs from the shortest path length of $s$ to $t$ by at-most $k$.

As the answer can be huge, you need to print it modulo $998244353$.

A path is a sequence of vertices $(v_1,v_2,v_3,\ldots,v_p)$ such that there exists an undirected edge $(v_i,v_{i+1})$ for $i=1,2,\ldots,p-1$.

Two paths differ, if they contain different number of vertices or there is an index $i$, where the edge $(v_i,v_{i+1})$ differs.

A path can visit the same vertex multiple times and even the initial vertex $s$ and final vertex $t$ can be visited multiple times. It is only required that you start at vertex $s$ and finish at vertex $t$ and maintain the path length constraint.

The graph doesn’t contain multi-edges and self loops.

The first line of the input contains a single integer $T(1 \le T \le 1000)$— the number of test cases.

The first line of each test case contains three integers $n,m$ and $k$$(2 \le n \le 2\times10^5, n-1 \le m \le 2\times10^5, 1 \le k \le 100)$ — the number of vertices, the number of edges and the path length constraint.

The next line contains two integers $s$ and $t$ $(1 \le s,t \le n, s \ne t)$— the initial vertex and final vertex.

The following $m$ lines describe the edges. Each contains three integers $u, v, w$ $(1 \le u,v \le n, u \ne v, 1 \le w \le 10^9)$ — the undirected edge $(u,v)$ and the weight of the edge.

It is guaranteed that there is at most one edge between any pair of vertices in the graph and the given graph is connected.

The sum of $n$ and the sum of $m$ over all testcases doesn't exceed $2\times10^5$.

For each testcase, print a single integer — the number of paths modulo $998244353$.

Input | Output |
---|---|

2 6 7 1 1 6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 3 5 2 2 4 3 7 10 6 1 7 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 2 5 2 3 5 2 4 6 3 5 7 4 | 3 332 |

Consider the first test case, $s=1, t=6$ and $k=1$. Shortest path length from $s$ to $t$ is $5$. Maximum allowed path length is $5+1 = 6$. Total three paths possible. $1 \to 2 \to 3 \to 4 \to 5 \to 6$. Length $5$. $1 \to 2 \to 3 \to 5 \to 6$. Length $5$. $1 \to 2 \to 4 \to 5 \to 6$. Length $6$. |

Login to submit.

75%
Solution Ratio

ash_98Earliest,

ChatGPTFastest, 2.5s

HSTU_TREENITYLightest, 108 MB

ChatGPTShortest, 1508B

Toph uses cookies. By continuing you agree to our Cookie Policy.