Obviously, the graph that they specify is too big. If a[i] equals 2, and b[i] equals 3, and N equals 1,000,000,000, then there are roughly (500,000,000 * 333,333,333) edges. That's too big.
However, let's work on building a different graph that solves the problem, but is much smaller. Here's thought number one: If your path uses an edge (w,x) defined by (a[i],b[i]), then it will never take a subsequent edge (y,z) which is also defined by (a[i],b[i]). Why? Because the edge (w,z) will exist, and your path could have taken it instead of (w,x).
That observation helps us, because we can try to define our path as a sequence of (a[i],b[i]) values, rather than as a sequence of edges.
So, let's build a new graph. In this new graph, the nodes are i values (as in (a[i],b[i])). We'll have an edge from S to a node i if the (a[i],b[i]) includes node S as one of its a[i] nodes. And, we'll have an edge from a node i to T the (a[i],b[i]) includes node T as one of its b[i] nodes. Finally, we'll have an edge from node i to node j if there exists a city that is one of the b[i] nodes, and also one of the a[j] nodes.
The shortest path from S to T on this new graph defines a shortest path on the original graph. The path on the original graph will be one edge shorter than the path our our new graph (we'll see this on the example below).
We can find this shortest path using BFS, which is O(|V|+|E|). Our new graph has a maximum of 1000 nodes, so the maximum number of edges is 1,000,000. That's big, but well within topcoder limits.
What about edges from node i to node j? We need to find a city C such that C is a multiple of b[i], and also a multiple of a[j]. In other words, we need to find the least common multiple (LCM) of b[i] and a[j]. If that value is less than or equal to N, then the edge exists. If it is greater to N, then the edge doesn't exist.
Is there a fast algorithm for LCM of x and y? Yes, and it is based on finding the greatest common denominator (GCD) of x and y? Suppose the GCD of x and y is z. Define s and t such that x = sz and y = tz. Then, the LCM of x and y is zst.
There is a fast algorithm (log time) for GCD. It is attributed to Euclid, and it goes as follows:
You can see the shortest path in red - since it is composed of five edges, the answer is four.