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.
1from heapq import heappop, heappush
2from collections import defaultdict
3
4def secondMinimum(n, edges, time, change):
5 graph = defaultdict(list)
6 for u, v in edges:
7 graph[u].append(v)
8 graph[v].append(u)
9
10 pq = [(0, 1)] # (current_time, node)
11 min_time = [float('inf')] * (n + 1)
12 second_min_time = [float('inf')] * (n + 1)
13 min_time[1] = 0
14
15 while pq:
16 curr_time, node = heappop(pq)
17
18 for neighbor in graph[node]:
19 # Calculate the time to wait if traffic light is red
20 wait_time = 0
21 if (curr_time // change) % 2 == 1:
22 wait_time = change - (curr_time % change)
23 new_time = curr_time + wait_time + time
24
25 if new_time < min_time[neighbor]:
26 second_min_time[neighbor] = min_time[neighbor]
27 min_time[neighbor] = new_time
28 heappush(pq, (new_time, neighbor))
29 elif min_time[neighbor] < new_time < second_min_time[neighbor]:
30 second_min_time[neighbor] = new_time
31 heappush(pq, (new_time, neighbor))
32
33 return second_min_time[n]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.
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.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
using namespace std;
int secondMinimumBFS(int n, vector<vector<int>>& edges, int time, int change) {
vector<vector<int>> graph(n + 1);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<int> first_min(n + 1, INT_MAX);
vector<int> second_min(n + 1, INT_MAX);
queue<pair<int, int>> q;
q.push({0, 1});
first_min[1] = 0;
while (!q.empty()) {
auto [curr_time, node] = q.front();
q.pop();
for (int neighbor : graph[node]) {
int wait_time = 0;
if ((curr_time / change) % 2 == 1) {
wait_time = change - (curr_time % change);
}
int new_time = curr_time + wait_time + time;
if (new_time < first_min[neighbor]) {
second_min[neighbor] = first_min[neighbor];
first_min[neighbor] = new_time;
q.push({new_time, neighbor});
} else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
second_min[neighbor] = new_time;
q.push({new_time, neighbor});
}
}
}
return second_min[n];
}This C++ adaptation employs breadth-first search, focusing on level-order operations enhanced by queue structures. It updates node transition times efficiently across iterations to tally and compare shortest available routes effectively.