### Loserinlife's blog

By Loserinlife, history, 5 months ago,

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

• 0

 » 5 months ago, # |   -10 I think that normal Dijkstra's algorithm can solve it.
•  » » 5 months ago, # ^ |   +1 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 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$.
 » 5 months ago, # |   0 Check this problem Modulo Shortest Path.