WCIPEG 2018 ECOO Qualifier
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
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
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
Input Specification
The first line of input will contain a single integer
The first line of each test case consists of two space separated integers,
The next
The following
Output Specification
For each test case, output one integer: the minimal cost for Ben Chau to
visit all programming competitions. Output -1
if it 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).
This yields a total cost of
Ben Chau cannot reach London in the second case, so it is impossible.
Comments