#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