All problems

Late Opening Bridges

Medium · shortest path

The island town of Marlow has n plazas, numbered 0 to n - 1, joined by footbridges. Each entry bridges[i] = [a, b, opens, cross] is a bridge between plazas a and b that can be walked in both directions.

A bridge is closed until minute opens; from that minute on it stays open for good. Crossing it takes cross minutes, and you may step onto it at any minute that is opens or later. You can wait as long as you like, at a plaza or at the foot of a bridge.

You start in plaza 0 at minute 0. Return the earliest minute at which you can be standing in plaza n - 1. If you can never get there, return -1. If n is 1, you are already there, so return 0.

Several bridges may join the same two plazas.

Examples

Example 1

Input: n = 3, bridges = [[0, 1, 5, 2], [1, 2, 0, 1], [0, 2, 20, 1]]

Output: 8

The bridge from plaza 0 to plaza 1 opens at minute 5, so you wait, cross during minutes 5 to 7, then cross to plaza 2 and arrive at minute 8. The direct bridge opens at minute 20 and would arrive at minute 21.

Example 2

Input: n = 3, bridges = [[0, 1, 0, 4]]

Output: -1

Plaza 2 has no bridge at all, so it cannot be reached.

Example 3

Input: n = 1, bridges = []

Output: 0

You start in plaza 0, which is also the last plaza.

Constraints