Subtask 2

Since there is one common station, we can find the one integer that appears in all ~R~ routes. Then, we can loop through all routes to find the starting and ending destinations. If they are on different routes, it takes 1 transfer, and if they are on the same route, it takes 0 transfers.

Time Complexity: ~\mathcal{O}(Q \times T^2)~

Subtask 3

Since there is at most one common station between any two routes, we can find said common station (if it exists). Then, we can perform a Dijkstra's algorithm on the graph.

Time Complexity: ~\mathcal{O}(T^2 + Q \times T log T)~

Full Solution

To store the graph, let all stations be the vertices of the graph. Next, an edge indicates a "track" (part of a route) connecting two stations. The edge should contain the two stations as the endpoints, but also the route. We can now run Dijkstra's on the graph. When we arrive at a new vertex, we check all edges connected to that vertex. Since we store the route of all edges, we can check if the current edge's route matches that of the previous edge's route. Our priority queue should prioritize travelling on the same route, since we are minimizing transfers.

Time Complexity: ~\mathcal{O}(Q \times T log T)~

Alternative Solution

Edit by AndyMan68:

Since there are no weights among the edges and we only care about prioritizing non-transfer routes, we can employ a technique known as 0/1 BFS to answer each query in ~\mathcal{O}(T)~.