Loserinlife's blog

Shortest path problem.
By Loserinlife, history, 14 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
14 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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$$$.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this problem Modulo Shortest Path.

→ Reply