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.
1function shortestPath(n, queries) {
2 const graph = Array.from({ length: n }, () => []);
3 for (let i = 0; i < n - 1; ++i) {
4 graph[i].push(i + 1);
5 }
6
7 function bfsDistance(start, end) {
8 let queue = [{ node: start, dist: 0 }];
9 let visited = Array(n).fill(false);
10 visited[start] = true;
11
12 for (let position = 0; position < queue.length; position++) {
13 const { node, dist } = queue[position];
14
15 if (node === end) return dist;
16
17 for (const neighbor of graph[node]) {
18 if (!visited[neighbor]) {
19 visited[neighbor] = true;
20 queue.push({ node: neighbor, dist: dist + 1 });
21 }
22 }
23 }
24 return -1;
25 }
26
27 let results = [];
28 for (const [u, v] of queries) {
29 graph[u].push(v);
30 results.push(bfsDistance(0, n - 1));
31 }
32 return results;
33}
34
35// Example usage
36const n = 5;
37const queries = [[2, 4], [0, 2], [0, 4]];
38console.log(shortestPath(n, queries));The JavaScript implementation similarly builds a dynamic graph representation and uses a breadth-first search to find the shortest path after each road addition query. The BFS is performed from node 0, updating the result for the path to node n-1.
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.