#2045
Second Minimum Time to Reach Destination
expert · 1130 · lc hard +32 · verified · 62.4% accepted · 1,319 likes · top 64%
Description
An undirected graph of n vertices (labeled 1 to n) has uniform edge traversal time time minutes. Each vertex's traffic signal alternates green/red every change minutes (starting green); you may depart only when green. You may revisit any vertex. Return the second minimum travel time from vertex 1 to vertex n (the smallest value strictly greater than the minimum time).
Example 1:
Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
Output: 13
Explanation:
The figure on the left shows the given graph.
The blue path in the figure on the right is the minimum time path.
The time taken is:
- Start at 1, time elapsed=0
- 1 -> 4: 3 minutes, time elapsed=3
- 4 -> 5: 3 minutes, time elapsed=6
Hence the minimum time needed is 6 minutes.
Example 2:
The red path shows the path to get the second minimum time.
- Start at 1, time elapsed=0
- 1 -> 3: 3 minutes, time elapsed=3
- 3 -> 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -> 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes.
Example 3:
Input: n = 2, edges = [[1,2]], time = 3, change = 2
Output: 11
Explanation:
The minimum time path is 1 -> 2 with time = 3 minutes.
The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.
Code
1
2
3