Loserinlife's blog

A cool shortest path problem
By Loserinlife, history, 11 months ago, In English

Given a weighted directed graph. Consider a vertice u connected to v1, v2, v3, ... with weight w1, w2, w3,.. You may permute the weight in any way you like. Ex: Edges from u are initially (u, v1, w1), (u, v2, w2), (u, v3, w3).. You can change it to (u, v1, w3), (u, v2, w1), (u, v3, w2). The weight must be permuted before the journey and remain that way through out the journey. Find the largest possible shortest path from 1 to n. Constraints: n <= 1e5, m <= 3e5 u , v <= n w <= 1e6 It sounds really cool but I have no idea how to solve it. Can someone help? Thanks :))

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We can remove the special edges from the graph and run SSP from 1 and do ans=dist1[n]. Then we run SSP from n in the same graph. Then for each vi connected to u we do ans=min(ans,dist1[u]+w+dist2[vi]) for every vi, where w is the minimum weight of an edge from u to some vi. This is because we either use a single special edge in the path or we don't. And if we do we just choose a permutation where this edge has the minimum possible weight assigned. And if

Because the graph has no negative weights cycles we need to visit u at most

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

This problem cam be solved on a DAG. Just do the basic dp. On a regular graph, I think you can do the same dp but with Dijkstra like algorithm where you go and calculate dp values from lowest to highest. Not sure how to avoid that going to O(N^2) or worse, but it might be possible.

→ Reply