Given a weighted undirected graph with N nodes and M edges (u, v, w) meaning node u and v is connected with weight w. Additionally, each node has a value a[i], and you can go from node i to node j with the cost of (a[i] + a[j]) % k, where k is a given constant. Find the shortest path from s to t

Constraints: N, M <= 2e5

a[i] < k <= 1e9

1 <= u, v, s, t <= n

w <= 1e9

Thanks

I think that normal Dijkstra's algorithm can solve it.

This is for all $$$n(n-1)/2$$$ pairs of vertices, meaning that the graph actually has $$$m + n(n-1)/2 = O(n^2)$$$ edges. Dijkstra runs in $$$O(E \log V)$$$ which is not fast enough if $$$E = O(V^2)$$$ and $$$V = 200\ 000$$$.

Check this problem Modulo Shortest Path.