Dijkstra Variation (Help Needed)

Revision en1, by Rafat, 2019-09-24 17:05:11

Problem: Given a weighted graph G, source node, destination node and a value X. find the shortest route from source to destination.

If there is a path from U to V with cost C, and you choose the path the value of X will change to X=gcd(X,C). So if the new X is less than the cost of next edge you can't pick the next edge. This way you have to find out the shortest path possible.

Node and Edges size can be up to 10^5 and the time limit is 5s. What's the idea to solve this problem??

For better understanding you can find the problem statement Here (Problem F)

Tags dijkstra modified, gcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Rafat 2019-09-24 17:05:11 693 Initial revision (published)