Shortest path problem.

Revision en1, by Loserinlife, 2023-09-20 14:54:07

Given a weighted undirected graph with N nodes and M edges (u, v, w) meaning node u and v is connected with weight v. 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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Loserinlife 2023-09-20 15:50:43 3 Tiny change: 'th weight v. Addition' -> 'th weight w. Addition'
en1 English Loserinlife 2023-09-20 14:54:07 413 Initial revision (published)