Skip to main content
Back to problems
#3243
Medium Algorithms

Shortest distance after road addition queries i

Array Breadth-First Search Graph Theory
61.9% acceptance
Feb 25, 2026
634
29
You are given an integer n and a 2D integer array queries. There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1. queries[i] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. After each query, you need to find the length of the shortest path from city 0 to city n - 1. Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

Solution

Rust
Time O(n * m)
Space O(n * m)
LeetCode
solution.rs 
impl Solution {
  pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut extra: Vec<Vec<usize>> = vec![vec![]; n];
    let mut result = Vec::with_capacity(queries.len());

    for q in &queries {
      extra[q[0] as usize].push(q[1] as usize);
      // BFS from 0 to n-1
      let mut dist = vec![i32::MAX; n];
      dist[0] = 0;
      let mut queue = std::collections::VecDeque::new();
      queue.push_back(0usize);
      while let Some(u) = queue.pop_front() {
        let d = dist[u];
        // built-in edge u -> u+1
        if u + 1 < n && dist[u + 1] == i32::MAX {
          dist[u + 1] = d + 1;
          queue.push_back(u + 1);
        }
        // extra edges
        for &v in &extra[u] {
          if dist[v] == i32::MAX {
            dist[v] = d + 1;
            queue.push_back(v);
          }
        }
      }
      result.push(dist[n - 1]);
    }
    result
  }
}