Description

Metro Meet-Up: Find the Fastest Station to Gather

Didier and his friends are exploring Taipei by metro, starting from different stations. They’ve agreed to spend the day together, but every extra minute spent riding separately is one less minute they can enjoy sightseeing, taking photos, and eating street food as a group. So, they’d like to choose a single meeting station that minimizes the total travel time for everyone combined.

You have exclusive access to the metro’s live timetable: a list of every direct ride between adjacent stations, its travel time, and the line it belongs to. With this information, and knowing that switching from one line to another always adds a fixed transfer penalty, you can compute the optimal meeting point and the best route for each friend.

The metro map is a graph:

• Node = station.
• Edge = direct ride between two adjacent stations on the same line.
• Each edge has
  • an integer ride-time (in minutes) and
  • a line-name (e.g., Red, Blue).

Whenever a passenger changes from one line to another at a station, a fixed transfer-penalty P minutes is added to their personal travel time.

Note: The first line they board does not incur a penalty.

Your task is to decide:

1. Which station everyone should meet at.
2. The individual route each friend should take.

At the end the total travel time (ride times + transfer penalties for all friends) should be minimized.

At least one station is reachable from every start station.

For this task a subset of stations has been selected from 6 of the lines, making a total of 77 stations (unique nodes) that ensure it contains all possible transfer stations between themselves. The transfer stations are marked with the two colors corresponding to the lines they connect. You can check them in the following table:

The following is a render of the resulting network graph from the subset of stations:

Note: The network graph does not correspond to the actual physical locations in the map, it just shows how the nodes are connected in between. Use this only as a reference, the input will be based in the structure of this network graph, you do not need to code all of this information.

 

Clarifications:

• Changing direction but staying on the same line at a station does not count as a transfer.
• There will always be one correct answer.
• Tie-break rule
  • When two stations give the same group total, compare the friends one by one, in input order:
    • Let’s say there are two candidate stations, if friend #1 needs less time to reach Station A than Station B, choose Station A.
    • If their times are equal, move on to friend #2, and so forth.
  • The first friend whose travel times differ decides the winner.

 

Test Cases (return here after reading all the quiz info):

1. Two friends, no transfer, order of friends matter.
2. Four friends, no transfer, order of friends matter.
3. Three friends, no transfer, unique solution.
4. Four friends, no transfer, unique solution.
5. Five friends, some transfer, all stations’ connections in the input, unique solution.

 

Input

First line:

m f P

• m - number of connections (edges) (1 ≤ m ≤ 88)
• f - number of friends (2 ≤ f ≤ 5)
• P - transfer penalty in minutes (1≤ P ≤ 20)

Assume the system will not always show the complete timetable with all station nodes, so the number of connections will vary from 1 to 88. The number 88 refers to the max number of edges with the 77 station nodes shown.

 

Next m lines describe each station’s connection:

from  to  time  lineName

• from, to - station names (strings without spaces, ≤ 256 chars)
• time - ride time in minutes (1 ≤ time ≤ 20)
• lineName - name of the line (string without spaces)

Note: Connections are bidirectional, which means you can ride both ways with the same time.

 

Next f lines are the boarding station of each friend:

friend_1_starting_station

…

friend_f_starting_station

 

Example 1 – Simple meet-up.

Input

3 2 4

Jiantan Yuanshan 4 Red

Yuanshan Minquan_W_Rd 3 Red

Daqiaotou Minquan_W_Rd 2 Orange

Jiantan

Daqiaotou

 

Example 2 – Transfer counts!

Input

13 2 4

Jiantan Yuanshan 3 Red

Yuanshan Minquan_W_Rd 2 Red

Minquan_W_Rd Shuanglian 2 Red

Shuanglian Zhongshan 2 Red

Zhongshan Taipei_Main_Station 2 Red

Taipei_Main_Station Shandao_Temple 3 Blue

Shandao_Temple Zhongxiao_Xinsheng 2 Blue

Zhongxiao_Xinsheng Zhongxiao_Fuxing 2 Blue

Jiannan_Rd Dazhi 3 Brown

Dazhi Songshan_Airport 2 Brown

Songshan_Airport Zhongshan_Junior_HS 3 Brown

Zhongshan_Junior_HS Nanjing_Fuxing 2 Brown

Nanjing_Fuxing Zhongxiao_Fuxing 2 Brown

Jiantan

Jiannan_Rd

 

Output

Lines in order:

minimal-total-time

meeting-station

route-1

...

route-f

1. minimal-total-time - the minimal sum of travel times (minutes) for all friends.
2. meeting-station - the chosen meeting station.
3. Following f lines (routes) - each friend’s path as
   Start->…->Meeting, using "->" between station names, without blank spaces, in the same order that their start stations were given.

 

Example 1 – Simple meet-up.

Output

• 9
• Minquan_W_Rd
• Jiantan->Yuanshan->Minquan_W_Rd
• Daqiaotou->Minquan_W_Rd

Explanation

Transfer penalty P = 4 minutes. In this case the best route did not require transferring, so it’s not needed.

No. Friend	Friend Starting Point	Route	Ride time	Transfers	Penalty	Personal total
1	Jiantan	Jiantan->Yuanshan->Minquan_W_Rd	4+3 = 7	0	0	7
2	Daqiaotou	Daqiaotou->Minquan_W_Rd	2	0	0	2
Total						9

 

Meeting anywhere else costs more because of the transfer penalty, so Minquan_W_Rd is the best option.

 

Example 2 – Transfer counts!

Output

• 34
• Taipei_Main_Station
• Jiantan->Yuanshan->Minquan_W_Rd->Shuanglian->Zhongshan->Taipei_Main_Station
• Jiannan_Rd->Dazhi->Songshan_Airport->Zhongshan_Junior_HS->Nanjing_Fuxing-> Zhongxiao_Fuxing->Zhongxiao_Xinsheng->Shandao_Temple->Taipei_Main_Station

 

Explanation

Transfer penalty P = 4 minutes.

There are two candidate meet-up stations with the same minimal total time to get there for the total group of friends. We optimize on the minimum of each friend’s time from top to bottom from the provided input.

Station	Friend #1 (Jiantan)	Friend #2 (Jiannan_Rd)	Group Total	Profile
Taipei_Main_Station	11 min	23 min	34	(34, 11, 23)
Zhongxiao_Fuxing	22 min	12 min	34	(34, 22, 12)

 

Because we are looking at the friend’s list in order, then the selected meet-up station is Taipei_Main_Station, because Friend #1 has the minimum time to travel to that station compared to the other candidate (check the tie-break-rule in the Clarifications section).

 

So the result can be viewed like this:

No. Friend	Friend Starting Point	Route	Ride time	Transfers	Penalty	Personal total
1	Jiantan	Red to Taipei_Main_Station	11	0	0	11
2	Jiannan_Rd	Brown to Zhongxiao_Fuxing -> Blue to Taipei_Main_Station	12 + 7 = 19	1	4	23
Total						34

 

Sample Input  Download

Sample Output  Download

Discuss