Learn
Exam

Bus Journey

Difficulty
INTERMEDIATE

Problem

Traveler Kim Soon-rye is exploring the Kingdom of NodeCrew. The kingdom has n cities and m buses. Each of the m buses operates between two distinct cities, traveling back and forth.

The positions of the cities are given in terms of their distances from Kim Soon-rye's starting location in the x direction (+x: east / -x: west) and the y direction (+y: north / -y: south), measured in meters.

Kim Soon-rye can travel between cities using buses or by walking. Write a function solution that calculates the estimated shortest time (in minutes) it will take for Kim Soon-rye to reach her destination city. The function should return the time truncated to three decimal places.

Assumptions for Kim Soon-rye’s journey include:

  1. Kim Soon-rye walks at a speed of 100 meters per minute.
  2. Buses do not allow boarding or alighting mid-journey; they only stop at their starting and ending cities.
  3. The distance between two cities separated by x in the east-west direction and y in the north-south direction is x2+y2(\sqrt{x^2 + y^2 \mathstrut }.
  4. There is no waiting time for boarding a bus.

Constraints

  • cities contains information for n cities, numbered from 1 to n:

    • Each element of cities is composed of the 'x distance and 'y distance from Kim Soon-rye's starting position.
    • The number of cities n is a natural number between 2 and 1,000 inclusive.
    • x and y are real numbers between -10,000 and 10,000 (meters), given to three decimal places.

  • buses contains information for m buses:

    • Each bus connects two cities and is described by the starting city number (s), the destination city number (e), and the travel time (time, in minutes) between the two cities.
    • s and e are natural numbers between 1 and n inclusive.
    • m is a natural number up to 50,000 inclusive.
    • time is a natural number up to 1,000 inclusive.

  • dest represents the city number Kim Soon-rye wishes to reach.

Test Case

Test Case Number cities buses dest answer
1 [[-5.457,-13.456],[93.551,-98.776],[92.740,87.973],[89.438,87.416]] [[1,3,1],[4,1,1]] 3 1.145
2 [[-0.635,97.175],[71.424,97.484],[-54.368,-85.041],[48.631,89.916],[-93.897,38.331]] [[1,4,1],[2,3,1],[3,4,1]] 4 1.022

Explanation for Test Case 1

  • Walking to city 1 takes 0.145 minutes. From city 1, taking a bus to city 3 takes 1 minute. Thus, the total time to reach city 3 is 1.145 minutes.

Explanation for Test Case 2

  • Walking directly to city 4 from the starting point takes 1.022 minutes. This is the fastest route.