Sponsored
Sponsored
This 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.
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.
1import java.util.*;
2
3public class SecondMinimumTime {
4 public int secondMinimum(int n, int[][] edges, int time, int change) {
5 List<Integer>[] graph = new ArrayList[n + 1];
6 for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
7 for (int[] edge : edges) {
8 graph[edge[0]].add(edge[1]);
9 graph[edge[1]].add(edge[0]);
10 }
11
12 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
13 pq.offer(new int[]{0, 1}); // (current_time, node)
14 int[] minTime = new int[n + 1];
15 int[] secondMinTime = new int[n + 1];
16 Arrays.fill(minTime, Integer.MAX_VALUE);
17 Arrays.fill(secondMinTime, Integer.MAX_VALUE);
18 minTime[1] = 0;
19
20 while (!pq.isEmpty()) {
21 int[] current = pq.poll();
22 int currTime = current[0], node = current[1];
23
24 for (int neighbor : graph[node]) {
25 int waitTime = 0;
26 if ((currTime / change) % 2 == 1) {
27 waitTime = change - (currTime % change);
28 }
29 int newTime = currTime + waitTime + time;
30
31 if (newTime < minTime[neighbor]) {
32 secondMinTime[neighbor] = minTime[neighbor];
33 minTime[neighbor] = newTime;
34 pq.offer(new int[]{newTime, neighbor});
35 } else if (newTime < secondMinTime[neighbor] && newTime > minTime[neighbor]) {
36 secondMinTime[neighbor] = newTime;
37 pq.offer(new int[]{newTime, neighbor});
38 }
39 }
40 }
41
42 return secondMinTime[n];
43 }
44}The Java solution follows a similar approach, using an adjacency list to represent the graph and a priority queue to implement a modified Dijkstra's search across potential paths. It stores the shortest and second shortest path times to each node in separate arrays, updating them based on the rules of traffic signal changes.
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.
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.
1const secondMinimum = (n,
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.