题目描述
A leading airline has hired you to write a program that answers the following query: given lists of city locations and direct flights, what is the minimum distance a passenger needs to fly to get from one given city to another? The city locations are specified by latitude and longitude.
To get from a city to another a passenger may take a direct flight if one exists; otherwise he must take a sequence of connecting flights.
Assume that if a passenger takes a direct flight from X to Y he never flies more than the geographical distance between X and Y. The geographical distance between two locations X and Y is the length of the geodetic line segment connecting X and Y. The geodetic line segment between two points on a sphere is the shortest connecting curve lying entirely on the surface of the sphere. Assume that the Earth is a perfect sphere of radius exactly 6,378 km, and that the value of is approximately 3.141592653589793. Round the geographical distance between every pair of cities to the nearest integer.
输入
The input may contain multiple test cases. The first line of each test case contains three integers N<=100, M<=300, and Q 10,000, where N indicates the number of cities, M represents the number of direct flights, and Q is the number of queries.
The next N lines contain the list of cities. The ith of these lines contains a string ci followed by two real numbers lti and lni, representing the city name, latitude, and longitude, respectively. The city name will be at most 20 characters and will not contain white-space characters. The latitude will be between -90 (South Pole) and +90 (North Pole). The longitude will be between -180 and +180, where negative (positive) numbers denote locations west (east) of the meridian passing through Greenwich, England.
The next M lines contain the direct flight list. The ith of these lines contains two city names aai and bi, indicating that there exists a direct flight from city ai to city bi. Both city names will occur in the city list.
The next Q lines contain the query list. The ith of these lines will contain city names ai and bi asking for the minimum distance a passenger needs to fly to get from ai to bi. Be assured that ai and bi are not equal and both city names will occur in the city list.
The input will terminate with three zeros for N, M, and Q.
输出
For each test case, first output the test case number (starting from 1) as shown in the sample output. Then for each input query, print a line giving the shortest distance (in km) a passenger needs to fly to get from the first city (ai) to the second one (bi). If there exists no route form ai to bi, just print the line “no route exists''.
Print a blank line between two consecutive test cases.
样例输入
3 4 2
Dhaka 23.8500 90.4000
Chittagong 22.2500 91.8333
Calcutta 22.5333 88.3667
Dhaka Calcutta
Calcutta Dhaka
Dhaka Chittagong
Chittagong Dhaka
Chittagong Calcutta
Dhaka Chittagong
5 6 3
Baghdad 33.2333 44.3667
Dhaka 23.8500 90.4000
Frankfurt 50.0330 8.5670
Hong_Kong 21.7500 115.0000
Tokyo 35.6833 139.7333
Baghdad Dhaka
Dhaka Frankfurt
Tokyo Hong_Kong
Hong_Kong Dhaka
Baghdad Tokyo
Frankfurt Tokyo
Dhaka Hong_Kong
Frankfurt Baghdad
Baghdad Frankfurt
0 0 0
样例输出
Case #1
485 km
231 km
Case #2
19654 km
no route exists
12023 km
参考代码
暂无
解析
暂无
