Show problems as
Classic problem #2045HardBreadth-First SearchGraph TheoryShortest PathDijkstra's AlgorithmK Shortest Path

Second Minimum Time to Reach Destination

Real-world version: Second-Quickest Run Past Timed Gates
Tracked in this browser only
Read Second Minimum Time to Reach Destination on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A yard has n depots numbered 1 through n. Each entry of edges is a pair of depots joined by a two-way run, and every run takes time minutes to travel. The yard is connected, so any depot can be reached from any other, and no run is listed twice.

Every depot has a gate that is open for change minutes, then shut for change minutes, over and over, starting open at minute 0. You may set off from a depot only while its gate is open; arriving is always allowed, and if you arrive while the gate is shut you wait for it to open again. Passing through a depot means leaving it, so the gate applies there too.

You set off from depot 1 at minute 0. Return the second smallest number of minutes in which depot n can be reached, counting only totals strictly larger than the smallest.

Examples

Example 1

Input
n = 7, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5], [5, 6], [6, 7], [5, 7]], time = 7, change = 9
Output
43

Depot 7 is four runs away at the quickest and five runs away next, so the answer follows the five-run route. The clock reaches 21 after three runs, which lands in a shut stretch, so it waits until 27 before the fourth run and again before the fifth.

Example 2

Input
n = 2, edges = [[1, 2]], time = 3, change = 2
Output
11

The one run reaches depot 2 at minute 3. Going back and forth takes three runs, and the waits at the shut gates push that total out further.

Example 3

Input
n = 4, edges = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], time = 1, change = 1
Output
3

Every depot joins every other, so depot 4 is one run away and next two runs away. The gate shuts for the whole of minute 1, so the second run cannot start until minute 2.

Constraints

  • 2 <= n <= 10^4
  • n - 1 <= edges.length <= 2 * 10^4
  • edges[i].length == 2
  • 1 <= edges[i][0] <= n
  • 1 <= edges[i][1] <= n
  • The two depots on a run are different
  • No run is listed twice
  • Every depot can be reached from every other
  • 1 <= time <= 10^3
  • 1 <= change <= 10^3

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def second_minimum(n: int, edges: list[list[int]], time: int, change: int) -> int:
Java
public int secondMinimum(int n, int[][] edges, int time, int change)

More on the same topics