Statistics

Problem Statement for "AirTravel"

Problem Statement

You are working for a shipping company, TopShipper, that specializes in shipping products by air. Your cargo jets transport items between a set of airports. From each airport, you can travel directly to some subset of the other airports. (Some airports may be too far, or may not have a safe passageway.) The ability to travel from one airport to another does not guarantee the ability to travel directly in the opposite direction.

You are about to send out a cargo plane on a trip to pick up a large shipment of a certain product. Unfortunately, only one other airport has this product for pickup, and you aren't guaranteed that there is a safe, direct route to the other airport. You may have to travel through one or more other airports to get to your final destination. Nonetheless, you wish to ultimately end up at the airport that has your desired product, and which you can get to by travelling the shortest possible distance.

You are to return a double indicating the number of miles travelled by the cargo plane along the optimal route from the origin to the destination. If no such route exists, return -1.

Given two coordinates, (lat1, lon1) and (lat2, lon2), the shortest distance between them is across an arc known as a great circle. The arclength along a great circle, between two points on the earth can be calculated as:

radius * acos(sin(lat1) * sin(lat2) + cos(lat1) * cos(lat2) * cos(lon1 - lon2))

For purposes of this problem, the radius of the earth is 4000 miles.

You are given the latitude and longitude coordinates of each airport in latitude and longitude. The i-th element of latitude corresponds to the i-th element of longitude. You are also given String[] canTravel. The i-th element of canTravel is a space-delimited list of the 0-based indices of the airports that can be reached from airport i. Finally, you are given origin and destination, the indices of the airports at which you start and end your trip.

Definition

Class:
AirTravel
Method:
shortestTrip
Parameters:
int[], int[], String[], int, int
Returns:
double
Method signature:
double shortestTrip(int[] latitude, int[] longitude, String[] canTravel, int origin, int destination)
(be sure your method is public)

Constraints

  • latitude, longitude, and canTravel will contain between 1 and 20 elements, inclusive.
  • latitude, longitude, and canTravel will each contain the same number of elements.
  • Each element of latitude will be between -89 and 89, inclusive.
  • Each element of longitude will be between -179 and 179, inclusive.
  • Each element of canTravel will be a space-delimited list of integers, with no leading zeroes.
  • Each integer represented in each element of canTravel will be between 0 and n - 1, where n is the number of elements in latitude.
  • origin and destination will be between 0 and n - 1, inclusive, where n is the number of elements in latitude.
  • No two airports will reside at the same latitude and longitude.

Examples

  1. {0, 0, 70}

    {90, 0, 45}

    {"2", "0 2", "0 1"}

    0

    1

    Returns: 10612.237799994255

    Here, we are looking to travel from airport 0 to airport 1. Using the given formula, we calculate that the distance from 0 to 1 is 6283, from 0 to 2 is 5306, and from 1 to 2 is 5306. A direct route from airport 0 to 1 would be fastest, if such a route were allowed. Since it is not, we have to travel through airport 2.

  2. {0, 0, 70}

    {90, 0, 45}

    {"1 2", "0 2", "0 1"}

    0

    1

    Returns: 6283.185307179586

    Here, we have the same three airports, and there is a safe route between any two. Thus, we take the direct route, which is quickest.

  3. {0, 30, 60}

    {25, -130, 78}

    {"1 2", "0 2", "1 2"}

    0

    0

    Returns: 0.0

    We are free to travel as we wish, but since our destination is the same as our point of origin, we don't have much travel to do.

  4. {0, 20, 55}

    {-20, 85, 42}

    {"1", "0", "0"}

    0

    2

    Returns: -1.0

    Notice here that we could go from airport 2 to airport 0, but not from 0 to 2. Given the available routes, there is no way we can get from airport 0 to airport 2.

  5. {77,32,-63,-45,-29,-72,-62,29,-77,-50,-84}

    {4,-51,67,-66,-21,-13,-70,-85,-81,17,-25}

    {"0 1 6 7 9 10","2 3 4 8","0 1 3 5 6 10","1 5 6 9 10","0 1 5 10","2 3 6 8","0 1 2 5 7 8","0 1 4 5 6 8","3 10","2 8 9","0 2 3 10"}

    8

    8

    Returns: 0.0

  6. {53,17,0,-87,-53,-73,88,62,-69,-9,76,-32,-72,-2,-72,-72}

    {-84,-67,-67,-7,69,-83,-42,29,35,25,19,-1,69,-44,-10,-65}

    {"3 4 7 10","4 5 8 9 10 14","2 7 9 11","0 2 3 4 6 7 8 11 12 14","2 3 4 5 7 8 9 10 11 14","0 1 3 4 5 6 13 14 15","0 3 4 6 7 8 9 10 12 13 14","2 3 4 6 9 10 11 12 13 15","0 3 6 11 14 15","0 2 4 5 6 9 10 11 15","2 3 4 7 9 10 11 12 13 14 15","0 3 4 5 7 8 12 13","1 2 4 6 8 12 15","1 2 5 8 9 10 13","3 4 6 9 10 11 13 14 15","1 2 3 9 12 13 14"}

    15

    8

    Returns: 2476.4572913155125

  7. {88,17,-80,39,55,56}

    {29,-13,-29,-16,0,-45}

    {"0 2","1 2 5","0 2 4","1 2 3","0 1 2 3","2 3 5"}

    2

    1

    Returns: 12239.008429056397

  8. {66,26,-11,-32,48,-27,-32,78,-7,89,0,-27,18,27,7,-7,61,-11,71,-8}

    {82,-74,-55,89,-47,50,48,35,-61,-60,-25,59,-49,54,-51,-43,-64,21,-37,32}

    {"0 7 9 10 12 15","0 1 5 6 8 9 10 13 16 17 18","1 3 5 7 8 10 11 12 19","0 4 7 8 9 10 11 15 16 17 19","0 1 2 4 5 8 10 11 12 15 18","4 6 7 9 10 11 12 17 19","1 2 3 7 10 11 12 13 17","1 2 5 10 12 19","1 2 4 5 6 7 8 9 10 11 13 18","4 10 12 14 15 16 17 19","0 4 5 6 9 12 13 14 16","3 6 7 10 13 16 17 18","0 1 2 4 7 14 15 16 18","1 3 4 6 7 9 10 11 13 16 17 19","0 2 3 4 8 11 12 15 16 19","0 2 4 5 7 11 14 15 17 19","1 2 3 9 10 14 17 18","0 1 2 3 4 5 8 10 11 12 15 18","0 7 11 14 16","0 3 4 7 8 12 14 16 17 18"}

    5

    3

    Returns: 2409.5245773235165

  9. {52,-20,86}

    {-9,-90,-24}

    {"0 1 2","2","1"}

    2

    0

    Returns: -1.0

  10. {-20,43,20,82,89}

    {63,55,-82,79,18}

    {"0 1 3","0 1","1 2 3","0 1","1 2 3 4"}

    1

    1

    Returns: 0.0

  11. {-5,27,-37,-86,-42,77,39,-46,-14,-41,1,27,-68,33,85,-19}

    {35,47,26,80,20,22,-9,14,50,-63,-76,-34,-89,-15,22,71}

    {"1 2 3 8 10 11 13 14 15","0 3 9 13 14 15","0 2 9 11 14","0 1 4 7 9 11 12 13 14 15","3 4 6 7 9 12","0 3 8 9 11 13","1 5 9 10 13 14","0 1 9 10 12 13 15","0 2 3 6 7 9 11 12","1 3 4 5 7 8 10 11 14","1 2 8 10 11 14","0 1 6 8 10 11 12 13 15","1 2 3 5 6 10 12 14 15","1 2 3 5 6 8 9 10 13 14","5 8 11","1 6 7 8 9 10 11 12 15"}

    15

    15

    Returns: 0.0

  12. {60,-66,60,-31,53,-4,-23,-33,-42,88,-33,-35,-78,0,-49,-15}

    {-18,45,90,61,-40,90,68,12,-48,80,65,-8,-37,59,-48,-8}

    {"0 2 3 6 8 9 10 14 15","2 3 5 6 7 9 10 12","0 3 4 5 8 10 11 13 14 15","1 2 5 7 9 14","0 3 5 6 7 8 14","0 1 4 6 10 11 13 14","2 4 5 6 8 9 10 12 13 14","6 8 12 13 14","0 2 5 6 7 8 10 11 14 15","0 1 2 3 4 5 6 11 13 14 15","0 2 3 4 5 6 7 8 10 13","0 3 4 7 8 9 11 13 14 15","1 2 4 6 7 8 9 12 13 15","0 2 3 5 7 8 9 11","0 1 5 6 7 10 11 12 13 15","5 6 9 11 13"}

    3

    7

    Returns: 2877.9825503801253

  13. {-40,73,-47,56}

    {52,-4,-7,4}

    {"1 3","1 2 3","1 2 3","1 2 3"}

    3

    1

    Returns: 1208.401739001028

  14. {-28,-71,-40,-30,26,38,-53}

    {17,85,26,73,-49,-71,-22}

    {"1 3 5 6","2 3 4","0 1 2 4","0 3 4","0 1 3 4 5 6","1 2 3 4 6","1 6"}

    1

    1

    Returns: 0.0

  15. {46,20,35,77,-7,-72,25,-78,-29,47,-87,-67,57}

    {23,44,-56,-58,-61,6,73,-84,62,90,-46,-86,-77}

    {"3 4 6 10 12","1 2 4 12","5 6 8","0 5 6 7 9 11 12","4 6 7 8 12","1 2 3 4 6 7 8 12","0 4 5 7 9","1 2 3 4 5 7 10 12","3 8 11","0 1 4 5 8 10","0 1 3 5 6 7 9 10 11 12","0 3 5 6 7 8 9 10 12","1 4 5 8 9 11 12"}

    9

    8

    Returns: 5591.335303331194

  16. {22,-20,10,21,84,46}

    {9,22,-52,-11,-4,-66}

    {"0 1 2 5","2 5","2 3 5","1 4 5","0 2","1 4"}

    1

    0

    Returns: 14417.45623332333

  17. {16,-8}

    {-81,-31}

    {"0","0"}

    1

    1

    Returns: 0.0

  18. {-82,-14,-9,-29,-13,58,63,16,15,74,-58,-74,66,80,39,57,79,-51,24}

    {-81,1,84,-31,-14,-48,-7,90,-59,88,-6,-8,28,-45,58,-51,-70,63,-25}

    {"3 7 9 11 14 18","0 1 2 5 6 7 9 13 14 16 18","4 6 7 9 11 13 14 15 17 18","0 1 3 6 7 8 12 13 14 16 18","2 4 6 8 12 17","0 2 6 7 8 10 13 14 16 18","1 3 4 5 7 9 10 13","2 3 4 5 6 11 13 14 17","3 5 9 11 12 13 14 15 18","1 2 3 4 5 7 8 11 12 13 18","2 3 6 7 10 13 14 15 16 17","0 1 2 4 5 6 9 10 13 16 17 18","4 6 7 16 17 18","2 4 7 8 10 13 14 15 16 17","0 7 10 12 15 17 18","1 2 4 5 6 7 8 10 11 13 14","0 2 3 4 5 6 7 8 10 11 12 13 14 15","0 2 3 4 5 7 8 9 10 11 12 13 15 18","1 2 3 4 7 9 11 12 15 16"}

    9

    16

    Returns: 1993.8025338562802

  19. {-17,50,-62,-3,-39,89,-46,-36,68,-30,-76}

    {-14,64,25,46,76,-77,-70,-57,-29,79,-23}

    {"0 4 10","0 1 2 5 9","0 1 2 3 5 6 7 8 9","5 6 8 9","0 2 5 6 7 8","1 2 3 6","0 1 5 10","0 1 2 3 4 5 7 9 10","1 3 5 6 7 8 9 10","1 2 3 4 5 6","1 2 4 8"}

    1

    7

    Returns: 11962.040343248767

  20. {2,-87,74,-13}

    {86,83,-29,30}

    {"1 3","0 2","1","0"}

    2

    0

    Returns: 17723.943245668233

  21. {-50,34,78,87,-8,-32}

    {-42,1,-1,17,5,42}

    {"0 1","0 4","0 1 2 3 5","1 2 5","0 1 2 4","2 3 4"}

    3

    5

    Returns: 8326.810439923662

  22. {19,-40,46,-37,-7,2,79,-22,14,-30,-54}

    {22,86,-90,65,73,16,-88,-7,-20,-4,6}

    {"1 2 4 5 8 10","0 3 4 6 7 9","0 3 6 7 9","0 1 2 4 6 10","0 4 5 6 7 8 9 10","2 6 7 9 10","5 6 8 9","2 4 7 8 9 10","1 2 4 5 7 9","2 3 4 6 7 8 9","3 7 9 10"}

    5

    8

    Returns: 4961.110536291824

  23. {-52,-45,19,-77,-47,-13,0}

    {-31,78,-38,-23,15,52,-66}

    {"1","0 2 4","0 1 2 3 5","0 6","6","0 1 4 6","0 1 2 3 4"}

    3

    2

    Returns: 7953.897459943442

  24. {-45,-75,-29,46,35,-43,13,-82,-76,7}

    {29,-46,-29,-6,-82,60,12,-84,55,-14}

    {"1 4 5 7 8","2 4 5 7 8","4 6 7 9","2 3 8","0 2 3 4 9","1 2 4 5 7 8","3 6 7 9","3 4 5 6 8 9","0 2 6 9","1 4 6 7 9"}

    4

    7

    Returns: 9622.559067480373

  25. {83,-72,-9,-46,56,86,60,-26,77,-1,72,6,2,25,-85,37,17,67,-61,-75}

    {-33,-34,-52,-84,-9,-46,32,-72,-66,50,8,-24,80,54,-10,-84,-76,-55,-87,-48}

    {"1 3 7 8 14 15 16 19","0 1 2 8 10 12 14 15 18 19","0 1 2 3 4 11 12 13 14 15 17 18","0 1 5 7 8 9 10 12 18 19","0 3 5 7 11 12 13 15 17 19","0 1 3 6 8 12 13 16 18 19","0 1 3 5 6 8 9 12 13 14 16 17","0 6 11 15 17","1 4 5 7 8 9 10 11 13 17 18 19","0 1 2 4 5 8 9 11 17","0 3 4 6 10 11 13 15 16 17","1 2 4 6 7 8 9 10 13 14 16 17 18","0 1 2 3 5 8 9 10 11 12 14 15 16 19","3 5 7 8 10 11 13 14","3 4 6 9 10 11 12 13 14 17 19","0 4 5 6 7 11 13 14 15 18","0 1 2 5 6 10 11 16 17","1 4 13 17 18 19","1 2 3 4 5 6 8 9 10 11 12 13 17 18","0 1 3 5 11 12 14 15 16 17 19"}

    14

    9

    Returns: 6039.205135480922

  26. {41,-63,-82,47,24,-10,-20,-25,-49,37,39,-33,57,63,61,0,59,-23,64}

    {84,-59,-26,-78,-77,57,43,-49,74,16,60,85,72,-40,-76,0,35,83,-73}

    {"1 7 11 14 15 18","1 3 7 8 10 11 14","0 2 3 4 5 7 8 9 10 13 14 15 16 17 18","0 1 3 5 7 9 10 15 16 17 18","0 3 5 6 7 9 10 11 12 14","1 2 4 5 7 8 9 10 11 14 15","0 2 5 6 7 12 15","1 2 3 4 5 7 13 14 16 17 18","1 2 3 4 8 10 12 13 15 18","1 5 7 9 10 11 16 17","0 2 3 4 6 12 13 17 18","0 1 2 3 4 5 6 8 9 10 12 14 15 16 17 18","0 1 2 6 7 8 15 16 17 18","1 2 3 4 5 6 8 12 13 15 17","0 1 2 3 4 5 7 9 13 14 15 17 18","1 3 7 12 13 15 17 18","3 8 12 13 15 18","2 3 6 8 12 13 14 15 17","1 3 5 6 7 10 11 12 13 15"}

    3

    9

    Returns: 4627.749316573995

  27. {-11,37,-4,68,-50,-4,-88,81,-56,-41}

    {50,-8,11,44,70,57,26,-43,-42,-73}

    {"1 2 3 6 8","1 3 4 9","0 1 2 4 5 6 7","1 2 3 5 7 8","3 5 6 7","0 2 4 5 6 7 8 9","2 6 7 8 9","1 6 8 9","1 4 6 7","0 5 9"}

    1

    5

    Returns: 8004.663144446447

  28. {0, 0, 70 }

    {90, 0, 45 }

    {"1 2", "0 2", "0 1" }

    0

    1

    Returns: 6283.185307179586

  29. {0, 30, 60 }

    {25, -130, 78 }

    {"1 2", "0 2", "1 2" }

    0

    1

    Returns: 9893.231024871204

  30. {0, 0, 70 }

    {90, 0, 45 }

    {"2", "0 2", "0 1" }

    0

    1

    Returns: 10612.237799994255

  31. {0, 20, 55 }

    {-20, 85, 42 }

    {"1", "0", "0" }

    0

    2

    Returns: -1.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: