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 ith element of latitude corresponds to the ith element of longitude. You are also given String[] canTravel. The ith element of canTravel is a spacedelimited list of the 0based 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  
 
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 spacedelimited 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  
0)  
 
1)  
 
2)  
 
3)  
