Need help in an interesting Graph Problem.

Revision en1, by GodSpeed98, 2018-11-30 09:43:05

I am stuck on this problem. https://www.codechef.com/problems/IOPC16K

Problem Statement:

Find out what will be the new shortest path if one of the edge on the original shortest path is removed.Find for all of the edges in shortest path path(Given Unique original shortest path).

Constraints:

no. of edge s<= 1e5 no. of nodes <= 1e5 weights of edges <= 1e9

I Looked at some of the AC solutions but could not get the Idea. So if somebody can share the Idea to solve the problem it would be very Helpful! (I think its on some Algorithmic Paper).

Tags #graph, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English GodSpeed98 2018-11-30 09:43:52 10
en1 English GodSpeed98 2018-11-30 09:43:05 651 Initial revision (published)