You are planning a business trip in which you need to visit clients in three cities.
The airline charges a separate rate for each individual leg of your journey.
For example, if you are flying from city A to city C, and
you land in city B along the way, then you will pay the fare for a flight
from A to B plus the fare for a flight from B to C.
The airline only sells round-trip tickets, so if you pay for a flight from A to B, then you
get a flight from B to A for free, whether you intend to use it or not. You want to calculate the minimum cost
needed to fly to your three destination cities and return home.
The prices of each possible flight are given as a String fares. The i-th element of
fares represents the prices of flights between city i and each of the other cities. In particular, character j of element i represents the price of a flight between city i and city j. Characters with ASCII
values between 49 (the character '1') and 122 (the character 'z') represent costs between $10 and $740, respectively. In particular, a character with ASCII value VAL represents the cost 10*(VAL - 48), measured in dollars. The special character '-' indicates that no flights are available between those two cities. For example, if fares contains the Strings
then it costs $70 to travel between cities 0 and 1, and $170 to travel between cities 1 and 2 ('A' has ASCII value 65). There are no direct flights between cities 0 and 2. fares is always symmetric; the cost to travel from city i to city j is always the same as the cost to travel from city j to city i.
The indices of the cities you intend to visit are given in a int destinations, which always contains exactly 3 elements. It is possible that more than one client lives in the same city, so the elements of destinations are not necessarily distinct. You live in city 0, and must begin and end your trip there.
Calculate and return the minimum cost to visit all three clients, or -1 if it is impossible to visit one or more of the clients.