FreeGuitars

TC China 08 - 1D · 2008-11-23 · by jthread

TC China 08 - 1D · 2008-11-23 · by jthread · Graph Theory

Show categories

Class Name: FreeGuitars

Return Type: int

Method Name: minimumCosts

Arg Types: (int, vector<string>)

Problem Statement

You are a guitar player and because you are really good, several music stores are giving you guitars for free! Unfortunately, you will have to travel to all the music stores to pick up your guitars. Because you don't have a drivers license and it's too far to go by bike, you decide to travel by train. But before you go, you first write a program to determine the minimum amount of money you have to spend to get to all the music stores by train.

You will be given an int N, the number of music stores there are (so also the numbers of guitars you get!), and a String[] trainRoutes, containing a list of train routes between the music stores. Each element of trainRoutes will be in the form of:
"STORE1 STORE2 TICKET" (quotes for clarity only)
STORE1 and STORE2 will be integers between 1 and N, inclusive, and TICKET will be the price for a round trip ticket from STORE1 to STORE2 and back. There will no more then 1 train route between each pair of stores, and there will not be a train route from a store to itself.

A round trip ticket is a ticket that allows you to travel the route in both directions exactly once. So buying a ticket between 3 and 5 means that you can travel from 3 to 5 one time, and from 5 to 3 one time. The 2 trips do not necessarily have to be in that order or directly after each other.

Return an int containing the minimum amount of money you will need to spend on train tickets to pick up all your free guitars. If it is not possible to pick up all N guitars, return -1. Initially, you are at store 1, and you want to return there after you picked up all guitars.

Constraints

N will be between 2 and 50, inclusive.
trainRoutes will contain between 1 and 50 elements, inclusive.
Each element of trainRoutes will be formatted "STORE1 STORE2 TICKET" (quotes for clarity).
Each STORE1 and STORE2 will be integers between 1 and N, inclusive, with no leading zeroes.
Each TICKET will be an integer between 0 and 100, inclusive, with no extra leading zeroes.
All elements of trainRoutes will describe different routes (so there will no more then 1 train route between each pair of stores).
No elements of trainRoutes will describe a route from a store to itself, so STORE1 never equals STORE2.

Examples

3
{"1 2 6", "1 3 4", "2 3 1"}
Returns: 5

Here we take the train from 1 to 3, pick up the guitar at 3, then go from 3 to 2, pick up the guitar, and go back to 3 and 2 (you already paid for those trips) to 1 (where you can pick up the last guitar).

3
{"1 3 56"}
Returns: -1

Whoops, we can not reach store 2!

5
{"1 2 88",
"1 3 37",
"1 4 73",
"1 5 58",
"2 3 59",
"2 4 30",
"2 5 98",
"3 4 28",
"3 5 85",
"4 5 82"}
Returns: 153

15
{"12 2 90", "14 4 11", "6 4 18", "5 8 35", "7 13 54", "11 2 33", "12 5 52",
 "13 2 98", "10 3 3", "4 7 63", "15 11 46", "11 7 4", "11 6 24", "9 7 30",
 "13 12 19", "5 10 82", "9 1 94", "13 3 30", "11 5 12", "10 1 10", "6 9 74",
 "12 8 55", "4 11 3", "12 4 71", "9 10 90"}
Returns: 306

11
{"1 2 1",
"1 3 64",
"1 4 43",
"1 6 63",
"1 7 5",
"1 8 81",
"1 9 18",
"1 10 95",
"1 11 35",
"2 3 59",
"2 4 15",
"2 5 15",
"2 6 24",
"2 7 14",
"2 8 83",
"2 9 90",
"2 10 85",
"3 4 85",
"3 5 28",
"3 6 36",
"3 8 81",
"3 9 25",
"3 10 28",
"3 11 62",
"4 5 5",
"4 6 11",
"4 7 84",
"4 8 81",
"4 9 70",
"4 10 38",
"4 11 39",
"5 6 7",
"5 7 9",
"5 9 48",
"5 10 35",
"5 11 9",
"6 7 36",
"6 8 83",
"6 9 84",
"6 10 98",
"6 11 4",
"7 8 83",
"7 9 94",
"7 10 80",
"7 11 34",
"8 9 20",
"8 10 34",
"8 11 46",
"9 11 91",
"10 11 64"}
Returns: 122

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

Coding Area

Language: C++17 · define a public class FreeGuitars with a public method int minimumCosts(int N, vector<string> trainRoutes) · 42 test cases · 2 s / 256 MB per case