Loserinlife's blog

A cool shortest path problem
By Loserinlife, history, 18 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

Comments Comments (1)
| Write comment?
»
14 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