Sponsored
Sponsored
This approach treats the problem as a graph traversal problem where each city is a node and roads are directed edges. Initially, the graph is linear, and each query introduces a single directed edge. We can use BFS to update and find the shortest path after each new road is added, recalculating the shortest path from node 0 to node n-1.
Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query.
Space Complexity: O(n + q), accounting for graph representation and BFS queue.
1from collections import deque
2
3def shortest_path(n, queries):
4 # Initialize graph with the default path 0 -> 1 -> ... -> n-1
5 graph = {i: [i + 1] for i in range(n - 1)}
6 graph[n-1] = []
7
8 def bfs_distance(start, end):
9 visited = [False] * n
10 queue = deque([(start, 0)])
11 visited[start] = True
12 while queue:
13 node, dist = queue.popleft()
14 if node == end:
15 return dist
16 for neighbor in graph[node]:
17 if not visited[neighbor]:
18 visited[neighbor] = True
19 queue.append((neighbor, dist + 1))
20 return -1 # If unreachable (should not happen)
21
22 answers = []
23 for u, v in queries:
24 graph[u].append(v)
25 answers.append(bfs_distance(0, n - 1))
26 return answers
27
28# Example usage
29n = 5
30queries = [[2, 4], [0, 2], [0, 4]]
31print(shortest_path(n, queries))This Python function shortest_path accepts the number of cities, n, and the list of queries that represent new road additions. The function maintains a dynamic graph representation and repeatedly performs BFS to determine the new shortest path from city 0 to city n-1 after each query.
This approach models the problem as a weighted graph and uses Dijkstra's algorithm, which is suitable since the graph predominantly has unit weights. This algorithm efficiently finds the shortest path from the start city to the end city after each new road is introduced, leveraging a priority queue to always expand the shortest known total distance path.
Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query.
Space Complexity: O(n + q), needed for graph representation and distance calculations.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
using namespace std;
vector<int> shortestPath(int n, vector<pair<int, int>>& queries) {
vector<vector<pair<int, int>>> graph(n);
for (int i = 0; i < n - 1; ++i) {
graph[i].emplace_back(i + 1, 1);
}
auto dijkstra = [&](int target) {
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[0] = 0;
pq.emplace(0, 0);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto& [v, weight] : graph[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.emplace(dist[v], v);
}
}
}
return dist[target];
};
vector<int> results;
for (auto& [u, v] : queries) {
graph[u].emplace_back(v, 1);
results.push_back(dijkstra(n - 1));
}
return results;
}
int main() {
int n = 5;
vector<pair<int, int>> queries = {{2, 4}, {0, 2}, {0, 4}};
vector<int> answer = shortestPath(n, queries);
for (int res : answer) {
cout << res << " ";
}
return 0;
}This C++ implementation of Dijkstra's algorithm uses a priority queue to determine the shortest path efficiently. Initially, the graph is set up with each city i and i+1 connected. For each query, a new edge is added, and the Dijkstra's algorithm recalculates the shortest path.