## Cheerio Contest 3 P5 - Train Network

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Java 3.0s
Python 3.0s
Memory limit: 512M

Author:
Problem types

In Toronto, the TTC operates a commuter train network with stations connected by bidirectional tracks. The stations are connected such that every pair of stations are connected by travelling along a sequence of tracks. Each track takes minute to traverse.

Union Station is the center of the network and is labelled node . Given the city's geography, all the tracks radiate outwards from downtown from west to east. The stations are numbered in ascending order based on its distance to Union Station. Stations that are at the same distance are numbered from west to east.

To improve the efficiency of the network, the TTC is considering adding a "crosstown" line, which will consist of a series of tracks that connect adjacent nodes that are the same distance from Union Station. Each track in the line will also take minute to traverse. To decide on the location of the line, they decide to ask queries. In the th query, they want to find the minimum time it takes for a commuter to travel from station to if the line was built at distance . Can you write a program to answer them?

for all

Points Awarded
2 points
2 points
11 points

#### Input Specification

The first line of input contains two integers and .

The next lines each contain two integers and , indicating a track connecting stations and .

The next lines each contain three integers , and .

#### Output Specification

For each query, output the minimum time in minutes on a separate line.

#### Sample Input

9 4
1 2
1 3
1 4
2 5
2 6
4 7
7 8
7 9
2 8 2
6 5 2
5 4 2
1 7 4

#### Sample Output

3
1
3
2

#### Explanation for Sample Output

Initially, the train network looks like this:

If the line was built at distance (the added tracks are coloured red), the network would look like this:

For the first query, the passenger can travel from in minutes.

For the second query, station is directly connected to station , thus only taking minute to travel.

For the third query, the passenger can travel from in minutes. Notice that the passenger can also travel from in the same amount of time.

For the fourth query, the passenger can travel from in minutes. There are no stations at a distance of so no new tracks would be added.