All problems

Metro Line Changes

Hard · shortest path

A metro system has n stations, numbered 0 to n - 1. Each ride is given as [a, b, line, minutes]: a train of line number line runs directly between stations a and b, in either direction, and the journey takes minutes. You may use the same ride as many times as you like.

You start at station start and want to reach station goal. Your first boarding is free. After that, every time you get off a train and board a train of a different line, you lose change extra minutes at that station. Riding on with the same line costs nothing extra.

Return the fewest total minutes needed to get from start to goal, counting ride times and line changes. If it cannot be done, return -1. If start and goal are the same station, the answer is 0.

There can be several rides between the same two stations, and a ride may start and end at the same station.

Examples

Example 1

Input: n = 4, rides = [[0, 1, 0, 5], [1, 2, 0, 5], [2, 3, 1, 4]], start = 0, goal = 3, change = 3

Output: 17

Ride line 0 from station 0 to station 2 (10 minutes), change to line 1 (3 minutes), then ride to station 3 (4 minutes).

Example 2

Input: n = 4, rides = [[0, 1, 0, 2], [1, 3, 1, 2], [0, 2, 2, 4], [2, 3, 2, 4]], start = 0, goal = 3, change = 5

Output: 8

Going through station 1 takes 2 + 2 minutes plus a 5 minute change. Staying on line 2 through station 2 takes 4 + 4 = 8 minutes and no change.

Example 3

Input: n = 3, rides = [[0, 1, 0, 2]], start = 0, goal = 2, change = 1

Output: -1

No train reaches station 2.

Constraints