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)
Since your title is Dijkstra variant, I assume you know about creating a state graph and running Dijkstra on it.
Whenever you are at a node two parameters are enough to define the state: the current node number and the current X.
So we consider a new graph where each node represents state (node, current_x ). For each edge u-v with say w weight in the original graph we would have an edge from (u,x) to ( v, gcd(x,w) ) if x>=w ; in this state graph.
Now we can run Dijkstra on this graph from (start,X). The answer would be the minimum of all the distances to (destination,c) nodes. That is all the state nodes that contain the destination in its parameter.
Running Time: All the intermediate X will be a factor of initial X. So the number of nodes and edges in the new graph is n*no_factors(X).
No factors = O( sqrt(X) ).
So running time would be n*sqrt(X) * log( n*sqrt(X) ).
Also X<=10^5 no_factors cant be more than 130. So we can replace sqrt(n) above with 130.
Problem Statement : https://justpaste.it/1p55p
How do I handle the cycle of the state graph?
Here's my code : https://ideone.com/sKnRzJ
If I add the cycles in the new graph,then Dijkstra fails to choose the correct path. Without cycles I get WA. Can you help me with that
What about problem A ?
any idea ?
Precalculate N%r for all r where r is prime or a perfect power. Then do CRT to find the rest of the modulo.
For example. 12 can be expressed as (3^1)*(2^2). This way every composite number can be expressed as the product of prime and perfect powers. And since we precalculated the modulo value for prime and perfect powers. Now we can use CRT to find the value of N%r with help of prime factors of r.
To understand how CRT solves this problem, you can get help from Here