An airplane exhaust CO2 (invisible) and water in condensation trails. Image in the public domain
At one of the many climate protests, Skylar fell in love with a fellow environmental activist. Unfortunately, the two young lovers live on opposite sides of the planet and long distance travel is only practical by (gasp) air. Skylar had scolded friends and family for flying, heavily handing out the recent Swedish export flygskam (verbatim translation: flight shame). But alas, the things we do for love! Now they want your help to calculate the minimum amount of flygskam Skylar will accumulate on a one-way trip across the globe.

To calculate the best route you models the planet as a perfect sphere and assumes that all flights fly at the distance $6381$ km from the center of the earth. The amount of shame for a single point-to-point flight is calculated as the distance between the airports in km, plus a take-off and landing penalty of $100$, that is, two airports with the flight distance $1000$ km will result in $1100$ shame.

Latitude and longitude

The positions of the airports are given as the latitude and longitude in (decimal) degrees. The latitude of a point $P$ on the earths surface is the angle between the equatorial plane and a line passing through $P$ and the center of the earth. The equator has latitude $0^\circ $, points north of the equator has positive values and points south of the equator has negative values, the North Pole has latitude $90^\circ $ and the South Pole latitude $-90 ^\circ $. Half circles that run from the North to the South pole are called meridians. The zero meridian runs through Greenwich. The longitude of a point $Q$ is the angle between the zero meridian plane and the line that run through $Q$ and the center of the earth, with values from $- 180^\circ $ to $+180^\circ $, with positive values east of Greenwich.


Input starts with one line with two integers $1 \leq N \leq 10\, 000$, the number of airports and $1 \leq M \leq 100\, 000$, the number of two-way flight routes. The second line has two strings $S$ and $T$, Skylar’s start position and Skylar’s target position. Then follows $N$ lines, each starts with a three letter (uppercase) airport code, followed by two real values numbers, the latitude and longitude in degrees. Then follows $M$ lines, each with two strings $a$ and $b$, the airports with a two-way flight connection.

All flight airports have unique names and all connections are between existing airports.


Output a real value with the minimum amount of flygskam Skylar will obtain on a one-way trip. If the target is unreachable and Skylar will be forever alone, output -1. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

Sample Input 1 Sample Output 1
4 4
ARN 59.6467921 17.9370443
SCR 61.156603 12.837360
CPH 55.618023 12.650763
OSL 60.197646 11.100008
Sample Input 2 Sample Output 2
2 1
AKL -37.006131 174.783781
LAX 33.941589 -118.408531
Sample Input 3 Sample Output 3
4 2
AKL -37.006131 174.783781
CDG 49.014490 2.542102
DXB 25.253176 55.365673
LAX 33.941589 -118.408531
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 4.8medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in