Skip to content

3243. Shortest Distance After Road Addition Queries I 👍

  • Time: $O(q(n + q))$
  • Space: $O(n + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
 public:
  vector<int> shortestDistanceAfterQueries(int n,
                                           vector<vector<int>>& queries) {
    vector<int> ans;
    vector<int> dist(n);
    vector<vector<int>> graph(n);

    iota(dist.begin(), dist.end(), 0);

    for (int i = 0; i < n - 1; ++i)
      graph[i].push_back(i + 1);

    for (const vector<int>& query : queries) {
      const int u = query[0];
      const int v = query[1];
      graph[u].push_back(v);
      if (dist[u] + 1 < dist[v]) {
        dist[v] = dist[u] + 1;
        bfs(graph, v, dist);
      }
      ans.push_back(dist[n - 1]);
    }

    return ans;
  }

 private:
  // Performs a BFS to update the shortest distances from the given `start` node
  // to all other reachable nodes in the graph. It updates the `dist` vector
  // with the new shortest distances.
  void bfs(const vector<vector<int>>& graph, int start, vector<int>& dist) {
    queue<int> q{{start}};
    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      for (const int v : graph[u]) {
        if (dist[u] + 1 < dist[v]) {
          dist[v] = dist[u] + 1;
          q.push(v);
        }
      }
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
    int[] ans = new int[queries.length];
    int[] dist = new int[n];
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i) {
      dist[i] = i;
      graph[i] = new ArrayList<>();
    }

    for (int i = 0; i < n - 1; ++i)
      graph[i].add(i + 1);

    for (int i = 0; i < queries.length; ++i) {
      final int u = queries[i][0];
      final int v = queries[i][1];
      graph[u].add(v);
      if (dist[u] + 1 < dist[v]) {
        dist[v] = dist[u] + 1;
        bfs(graph, v, dist);
      }
      ans[i] = dist[n - 1];
    }

    return ans;
  }

  // Performs a BFS to update the shortest distances from the given `start` node
  // to all other reachable nodes in the graph. It updates the `dist` vector
  // with the new shortest distances.
  private void bfs(List<Integer>[] graph, int start, int[] dist) {
    Queue<Integer> q = new LinkedList<>(Arrays.asList(start));
    while (!q.isEmpty()) {
      final int u = q.poll();
      for (final int v : graph[u]) {
        if (dist[u] + 1 < dist[v]) {
          dist[v] = dist[u] + 1;
          q.offer(v);
        }
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  def shortestDistanceAfterQueries(
      self,
      n: int,
      queries: list[list[int]],
  ) -> list[int]:
    ans = []
    dist = list(range(n))
    graph = [[] for _ in range(n)]

    for i in range(n - 1):
      graph[i].append(i + 1)

    for u, v in queries:
      graph[u].append(v)
      if dist[u] + 1 < dist[v]:
        dist[v] = dist[u] + 1
        self._bfs(graph, v, dist)
      ans.append(dist[n - 1])

    return ans

  def _bfs(self, graph: list[list[int]], start: int, dist: list[int]) -> None:
    """
    Performs a BFS to update the shortest distances from the given `start` node
    to all other reachable nodes in the graph. It updates the `dist` vector
    with the new shortest distances.
    """
    q = collections.deque([start])
    while q:
      u = q.popleft()
      for v in graph[u]:
        if dist[u] + 1 < dist[v]:
          dist[v] = dist[u] + 1
          q.append(v)