A  group  of  people  plan  to  have  a  vacation  in  a  remote  island  near  the  equator  over  the  winter  holiday.  All members  of  the  group  live  in  different  countries  and  the  destination  island  is  only  reachable  via  airplane. Therefore, each member has to go to their own country’s airport to take a flight to the destination island. We assume that each country has only one airport. Now, for the sake of holiday spirit, all group members agree to start the journey on the same day from their home cities. Also, they plan to be at their country’s airports on the same  day,  which  is  not  necessarily  the  first  day  of  their  travel.  However,  the  airports  might  not  be  in  each member’s home city, so some members may have to travel to another city over the course of a few days. On the  first  day  of  the  winter  holiday,  all  members  are  in  their  respective  home  cities.  Then,  every  day,  each member  has  to  individually  decide  between  traveling  to  an  adjacent  city  (meaning  that  the  two  cities  are connected by a road), or staying the day in the city they are currently in. Since the travelling cost between two adjacent  cities  and  the  cheapest  hotel  price  in  each  city  are  already  known  to  the  world,  one  knows  exactly how much it will cost either to move to an adjacent city or to stay in that city for each day. All members want to  have  as  much  money  as  possible  for  the  vacation  on  the  island,  so  they  pool  their  money  together  and decide to calculate the travel plans as a group. Their goal is that all the members end up at their designated countries’ airports on the same day, while spending the least amount of money. 

Consider  an  example  in  Figure  L.1  with  two  members  and  their  designated  airports  being  in  cities  4  and  3, respectively. The cheapest travel plans with both members starting in their hometowns (always city 1) would be:  (day  1)  member-1  moves  to  city  3,  member-2  moves  to  city  2; (day  2)  member-1  moves  to  city  4, member-2 moves to city 1; (day 3) member-1 stays at city 4, member-2 moves to city 3. This has cost (1+5+1)+(3+2+4)=16.
 Note  that  the  travelling  cost between  two  cites  is  not  necessary  symmetric.  Additionally,  no  city  has  a  road connecting it to itself. You can always assume that, in each country, there is at least one path from home to the designated airport.
  You should write a program that finds the minimum cost required to get all members from their home city to their  country’s  designated  airport  such  that  everyone is  at  the airport  on  the  same  day.  Note  that  every  day, one has to either move to an adjacent city or stays at the current city hotel.