Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 27

Description

Shortest Distance After Road Addition Queries I

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.

Example 1:

Example 2:

Constraints:

• 3 <= n <= 500
• 1 <= queries.length <= 500
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• There are no repeated roads among the queries.

Solution

class Solution {
public:
  vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
    vector<vector<int>> neighbors(n);
    for(int i = 0; i < n - 1; ++i) {
      neighbors[i].push_back(i + 1);
    }

    vector<int> distance(n);
    iota(distance.begin(), distance.end(), 0);

    vector<int> answer;
    answer.reserve(queries.size());

    for(const auto &query : queries) {
      int src = query[0];
      int dst = query[1];
      neighbors[src].push_back(dst);
      
      if(distance[src] + 1 < distance[dst]) {
        queue<int> q;
        q.push(dst);
        distance[dst] = distance[src] + 1;
        while(q.size()) {
          auto cur = q.front();
          q.pop();
          for(auto nxt : neighbors[cur]) {
            if(distance[cur] + 1 >= distance[nxt]) continue;

            q.push(nxt);
            distance[nxt] = distance[cur] + 1;
          }
        }
      }
      answer.push_back(distance.back());
    }
    return answer;
  }
};