Triptych

TCCC05 Round 4 · 2005-01-10 · by vorthys

TCCC05 Round 4 · 2005-01-10 · by vorthys · Graph Theory

Show categories

Class Name: Triptych

Return Type: int

Method Name: minCost

Arg Types: (vector<string>, vector<int>)

Problem Statement

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

    "-7-"
    "7-A"
    "-A-"

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.

Constraints

fares contains between 3 and 50 elements, inclusive.
Each element of fares contains exactly N characters, where N is the number of elements in fares.
Each character in fares is either '-' or has an ASCII value between 49 ('1') and 122 ('z'), inclusive.
The character '\' (ASCII 92) does not appear in fares.
Character i of element j of fares is equal to character j of element i, for all indices i and j.
Character i of element i of fares is '-', for all indices i.
destinations contains exactly 3 elements.
Each element of destinations is between 0 and N-1, inclusive.

Examples

{ "-123", "1-23", "22-1", "331-" }
{ 1,2,3 }
Returns: 40

{ "-7-",
  "7-A",
  "-A-" }
{ 1, 2, 1 }
Returns: 240

You fly from city 0 to city 1 for $70, and visit both client 0 and client 2. Then you fly from city 1 to city 2 for $170, and visit client 1. Finally, you return home to city 0, with a layover in city 1.

{ "-8--9",
  "8---7",
  "---5-",
  "--5--",
  "97---" }
{ 1, 3, 4 }
Returns: -1

You can reach cities 1 and 4, but you can't get to city 3.

{ "-5777",
  "5-555",
  "75-88",
  "758-8",
  "7588-" }
{ 2, 3, 4 }
Returns: 200

You could fly directly to each client's city and return home in between visits for a cost of $210. However, you can make all the visits for only $200 by flying to city 1 and using that as a hub to fly to the other cities.

{ "-123",
  "1-45",
  "24-6",
  "356-" }
{ 0, 0, 0 }
Returns: 0

All the clients live in your own city, so no flights are necessary.

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Triptych with a public method int minCost(vector<string> fares, vector<int> destinations) · 70 test cases · 2 s / 256 MB per case