Wcipeg 2018 ECOO Qualifier

IOI Tour

This year, the organizers for the IOIO or International Olympiad in Informatics of Ontario, the council known by their clever acronym OIOIO, Organization for International Olympiad in Informatics of Ontario, has decided to add a bit of spice to the programming competitions this year.

For this year's programming circuit, there will be M (1 ≤ M ≤ 30) international host cities, each hosting exactly one programming event. Each city, i, will be identified by its single non-space separated name, S_i, and will host a tournament for this year's circuit. Cities are inputted by order of their competition, with the first happening before the second.

All competitors will visit all host cities to participate in all competitions, flying to each host city after the other following the order of their tournaments. There are K (1 ≤ K ≤ 500) number of flights available. Each flight, f, will connect cities A_f and B_f with a cost of C_f (1 ≤ C_f ≤ 1 000), meaning competitors can travel bidirectionally from A to B, B to A for C_f. Flights may connect cities that are not host cities, but must nonetheless be considered in travel plans, for connecting flights are possible. At most one flight will exist between any two cities. The total number of cities with flights is guaranteed to be at most 50.

Your task is to help out Ben Chau, an aspiring programmer who wishes to complete this year's circuit. Ben Chau will begin this year's circuit in Toronto. What is the minimal cost for Ben Chau to attend the programming competitions in all M host cities with K available flights? The cost is the sum of all his flight costs, including the final trip back to Toronto.

Input Format:

T (1 ≤ T ≤ 10), followed by T test cases. Each case consists of the following: M (1 ≤ M ≤ 30), K (1 ≤ K ≤ 500) For the next M lines: For each host city i, the name, S_i (No more than 50 characters long, no spaces). For the next K lines: For each flight f, the two connected cities, A_f, B_f, and the cost, integer C_f (1 ≤ C_f ≤ 1 000).

Output Format:

For each test case, output one integer: the minimal cost for Ben Chau to visit all programming competitions. Output -1 if is impossible for Ben Chau to visit all competitions.

Sample Input:

3
4 6 
Toronto 
Boston 
Miami
Orlando
Toronto Boston 1
Boston Orlando 4
Toronto Orlando 5
Toronto Chicago 8
Miami Chicago 3
Boston Chicago 1
1 1
London
Toronto Newcastle-Upon-Tyne 1000
6 15 
Vancouver
ThunderBay
Waterloo
Yellowknife
Edmonton
Calgary
Toronto Calgary 223
Sudbury Iqaluit 507
Montreal Yellowknife 624
Winnipeg Montreal 340
ThunderBay Waterloo 640
ThunderBay Winnipeg 330
Iqaluit Edmonton 667
Montreal Ottawa 784
Sudbury Ottawa 202
Windsor Vancouver 777
Montreal St.John's 484
London Yellowknife 661
Ottawa Windsor 201
Sudbury Toronto 42
London Quebec 724

Sample Output:

18
-1
10674

To complete the first test case most optimally: Ben Chau stays in Toronto for the first competition (+0). He flies directly to Boston. (+1). Flies Boston ? Chicago ? Miami for the third competition (+4). Flies Miami ? Chicago ? Boston ? Orlando for the last competition (+8). He takes the direct flight back to Toronto (+5). 0 + 1 + 4 + 8 + 5 = 18 Ben Chau cannot reach London in the second case, so it is impossible.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jan 28, 2018
Author: williamh

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)