A Trip Through Tunnels

Medium

You stand on a plane at point start = [x, y] and want to reach point finish. Walking from (x1, y1) to (x2, y2) costs |x2 - x1| + |y2 - y1|. There are also tunnels: tunnels[i] = [x1, y1, x2, y2, cost] is a one-way tunnel from (x1, y1) to (x2, y2) that costs cost to ride. Each tunnel can be used any number of times, or not at all. Return the minimum cost of getting from start to finish.

Example 1

start=[1, 1], finish=[9, 3], tunnels=[[2, 1, 8, 3, 2], [8, 3, 1, 1, 1]] → 4

Walk to the first tunnel's entrance (2, 1) for 1, ride it for 2, then walk from its exit (8, 3) to the finish for 1. That is 4 instead of 10 on foot. The second tunnel goes the other way and does not help.

Example 2

start=[5, 5], finish=[6, 7], tunnels=[[5, 5, 6, 7, 10]] → 3

The tunnel costs 10, while walking takes only |6 − 5| + |7 − 5| = 3.

Example 3

start=[1, 1], finish=[20, 20], tunnels=[[1, 2, 10, 10, 3], [10, 11, 20, 19, 3], [12, 12, 1, 1, 1]] → 9

Constraints

len(start) = len(finish) = 2
1 ≤ len(tunnels) ≤ 400
len(tunnels[i]) = 5
all coordinates and costs are integers from 1 to 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Array Shortest Path Heap (Priority Queue)

Similar problems

Shortest Path of a Rolling Ball Medium Most Reliable Relay Route Medium Souvenir Round Trip Medium Nearest Flagged Node Medium Stops That Close Medium

Input

start=[1, 1], finish=[9, 3], tunnels=[[2, 1, 8, 3, 2], [8, 3, 1, 1, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 57 tests on the server, hidden ones included.