Shortest Distance After Road Addition Queries I
Problem
There are n cities numbered 0 to n-1. Initially there is a one-way road from every city i to city i+1, so the only way to travel is forward step by step. Each query [u, v] adds a new one-way road from u to v (with u < v). After processing each query, return the length of the shortest path from city 0 to city n-1 measured in number of roads. The answer to each query is independent of later queries but the roads accumulate.
n = 5, queries = [[2,4],[0,2],[0,4]][3, 2, 1]from collections import deque
def shortest_distance(n, queries):
adj = [[i + 1] for i in range(n - 1)]
adj.append([])
ans = []
for u, v in queries:
adj[u].append(v)
dist = [-1] * n
dist[0] = 0
q = deque([0])
while q:
x = q.popleft()
for y in adj[x]:
if dist[y] == -1:
dist[y] = dist[x] + 1
q.append(y)
ans.append(dist[n - 1])
return ansfunction shortestDistance(n, queries) {
const adj = Array.from({ length: n }, (_, i) => i < n - 1 ? [i + 1] : []);
const ans = [];
for (const [u, v] of queries) {
adj[u].push(v);
const dist = new Array(n).fill(-1);
dist[0] = 0;
const q = [0];
let head = 0;
while (head < q.length) {
const x = q[head++];
for (const y of adj[x]) {
if (dist[y] === -1) {
dist[y] = dist[x] + 1;
q.push(y);
}
}
}
ans.push(dist[n - 1]);
}
return ans;
}class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
if (i < n - 1) adj.get(i).add(i + 1);
}
int[] ans = new int[queries.length];
for (int qi = 0; qi < queries.length; qi++) {
adj.get(queries[qi][0]).add(queries[qi][1]);
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
Deque<Integer> q = new ArrayDeque<>();
q.add(0);
while (!q.isEmpty()) {
int x = q.poll();
for (int y : adj.get(x)) {
if (dist[y] == -1) {
dist[y] = dist[x] + 1;
q.add(y);
}
}
}
ans[qi] = dist[n - 1];
}
return ans;
}
}class Solution {
public:
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) adj[i].push_back(i + 1);
vector<int> ans;
for (auto& qr : queries) {
adj[qr[0]].push_back(qr[1]);
vector<int> dist(n, -1);
dist[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int y : adj[x]) {
if (dist[y] == -1) {
dist[y] = dist[x] + 1;
q.push(y);
}
}
}
ans.push_back(dist[n - 1]);
}
return ans;
}
};Explanation
The cities form a line: from city i you can always step to i+1. Every query adds one extra forward road as a shortcut, and after each addition we want the fewest roads needed to get from city 0 to city n-1.
Because every road counts as one step (unit weight), the shortest path is exactly what a breadth-first search finds. BFS explores the graph in waves: all cities reachable in 1 road, then 2 roads, and so on, so the first time it reaches n-1 it has used the minimum number of roads.
We keep an adjacency list. Each query appends its shortcut edge to that list permanently (roads accumulate), then we run a fresh BFS from city 0. A dist array marks each city's distance, initialized to -1 (unseen) except dist[0] = 0. We pop a city, and for each road leaving it we set the neighbor's distance one larger the first time we see it.
After the BFS drains, dist[n-1] is the answer for that query. We record it and move on, carrying the accumulated roads into the next query.
Worked example: n = 5. After adding [2,4] the path 0→1→2→4 uses 3 roads. After also adding [0,2], 0→2→4 uses 2. After adding [0,4], the direct hop 0→4 uses 1. Output [3, 2, 1].