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

#include <iostream>
#include <vector>
#include <numeric>

class Solution {
public:
    std::vector<int> shortestDistanceAfterQueries(int n, std::vector<std::vector<int>>& queries) {
        int m = queries.size();
        std::vector<int> dp(n);
        std::iota(dp.begin(), dp.end(), 0);
        std::vector<std::vector<int>> adj(n);
        std::vector<int> res(m);
        
        for (int i = 0; i < m; ++i) {
            adj[queries[i][1]].push_back(queries[i][0]);
            if (dp[queries[i][0]] + 1 < dp[queries[i][1]]) {
               dp[queries[i][1]] = dp[queries[i][0]] + 1;
               for (int j = queries[i][1] + 1; j < n; ++j) {
                   dp[j] = std::min(dp[j], dp[j - 1] + 1);
                   for (auto& k : adj[j]) {
                       dp[j] = std::min(dp[j], dp[k] + 1);
                   }
               }
            }
            res[i] = dp.back();
        }        
        return res;
    }
};