A cool shortest path problem

Revision en1, by Loserinlife, 2023-06-02 12:39:50

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 :))

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Loserinlife 2023-06-02 12:39:50 610 Initial revision (published)