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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
public int SecondMinimum(int n, int[][] edges, int time, int change) {
var graph = new List<int>[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new List<int>();
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
var firstMinTime = new int[n + 1];
var secondMinTime = new int[n + 1];
Array.Fill(firstMinTime, int.MaxValue);
Array.Fill(secondMinTime, int.MaxValue);
firstMinTime[1] = 0;
var queue = new Queue<(int, int)>(); // (current_time, node)
queue.Enqueue((0, 1));
while (queue.Count > 0) {
var (currTime, currNode) = queue.Dequeue();
foreach (var neighbor in graph[currNode]) {
int waitTime = 0;
if ((currTime / change) % 2 == 1) {
waitTime = change - (currTime % change);
}
int newTime = currTime + waitTime + time;
if (newTime < firstMinTime[neighbor]) {
secondMinTime[neighbor] = firstMinTime[neighbor];
firstMinTime[neighbor] = newTime;
queue.Enqueue((newTime, neighbor));
} else if (newTime > firstMinTime[neighbor] && newTime < secondMinTime[neighbor]) {
secondMinTime[neighbor] = newTime;
queue.Enqueue((newTime, neighbor));
}
}
}
return secondMinTime[n];
}
}This C# implementation adopts BFS strategy supplemented with queue mechanics to facilitate transition timing. It captures path times into arrays to discern shortest travel durations under dynamic traffic signal conditions.