#3604

Minimum Time to Reach Destination in Directed Graph

medium · 45.5% accepted · 102 likes · top 29%

graph theory · heap (priority queue) · shortest path

Description

You are given an integer n and a directed graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, starti, endi] indicates an edge from node ui to vi that can only be used at any integer time t such that starti <= t <= endi.

You start at node 0 at time 0.

In one unit of time, you can either:

- Wait at your current node without moving, or

- Travel along an outgoing edge from your current node if the current time t satisfies starti <= t <= endi.

Return the minimum time required to reach node n - 1. If it is impossible, return -1.

Solution