Subway
Time limit1sMemory limit128 MB
Find the shortest travel time from home to school using walking and subway lines, rounding the answer to the nearest minute.
- Level
Medium4 of 10
- Topics
- Shortest path, Graph, Geometry, Implementation
- Solved
- No attempts yet
Problem
You have just moved from a quiet neighbourhood to a big, noisy city. Instead of biking to school, you now have to walk and ride the subway, and you want to know how long the trip will take.
You walk at a speed of 10 km/h and the subway travels at 40 km/h. Assume you are lucky: whenever you reach a subway stop, a train is already there and you can board immediately. You may board and leave the subway any number of times and switch between different subway lines freely. Every subway line runs in both directions.
You may walk in a straight line between any two points, but you can only board or leave the subway at a stop.
Input
The input is a stream of integers separated by whitespace; the numbers may be split across several lines.
The first two integers are the and coordinates of your home, and the next two are the and coordinates of your school.
After that come one or more subway lines. Each subway line is given as the coordinates of its stops, in order along the line, and is terminated by the sentinel pair -1 -1. Every coordinate is a non-negative integer number of metres, adjacent stops are joined by a straight subway segment, and each line has at least two stops. There are at most subway stops in the whole city.
Output
Print a single integer: the time in minutes for the fastest possible trip from home to school, rounded to the nearest minute.