A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes.
Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.
The second minimum value is defined as the smallest value strictly larger than the minimum value.
[2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.
Notes:
1 and n.
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. 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 2:
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.
Constraints:
2 <= n <= 104n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)edges[i].length == 21 <= ui, vi <= nui != vi1 <= time, change <= 103This approach involves using a priority queue to simulate a modified version of Dijkstra's algorithm, aiming to track both the shortest and second shortest path times to the last node. The cost of each step is affected by traffic signal delays, calculated based on the cumulative time spent traveling.
This solution builds a graph using an adjacency list. We use a priority queue to explore paths encapsulated by their current time and destination node. For each node, we maintain two arrays to keep track of the first and second minimum time taken to reach it. The algorithm updates these values by considering wait times if a traffic light is red. We return the second minimum time to reach the destination node.
Java
C++
C
The time complexity is O(E log V), where E is the number of edges, and V is the number of vertices, due to the priority queue operations. The space complexity is O(V + E) due to the storage of the adjacency list and the min_time/second_min_time arrays.
This approach leverages a Breadth-First Search (BFS) to explore paths in level order, carefully managing path times with respect to traffic signal cycles. Time values are stored to identify both the shortest and second shortest paths throughout the search.
This JavaScript solution employs BFS with time management using traffic signal states to uncover the minimum and second minimum path costs. Paths are explored level by level, with state transitions manipulated using queue operations.
C#
C++
The time complexity is O(E) due to the traversal of all edges and the space complexity is O(V + E) for graph and time-tracking arrays.
| Approach | Complexity |
|---|---|
| Modified Dijkstra's Algorithm | The time complexity is O(E log V), where E is the number of edges, and V is the number of vertices, due to the priority queue operations. The space complexity is O(V + E) due to the storage of the adjacency list and the min_time/second_min_time arrays. |
| Breadth-First Search with Traffic Signal Consideration | The time complexity is O(E) due to the traversal of all edges and the space complexity is O(V + E) for graph and time-tracking arrays. |
Meeting Rooms II - Leetcode 253 - Python • NeetCode • 174,315 views views
Watch 9 more video solutions →Practice Second Minimum Time to Reach Destination with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor