/**
* @param {number} n
* @param {number[][]} queries
* @return {number[]}
*/
var shortestDistanceAfterQueries = function(n, queries) {
let neighbors = new Array(n).fill().map(() => []);
for (let i = 0; i < n - 1; i++) {
neighbors[i].push(i + 1);
}
let res = [];
for (let i = 0; i < queries.length; i++) {
neighbors[queries[i][0]].push(queries[i][1]);
res.push(bfs(n, neighbors));
}
return res;
};
var bfs = function(n, neighbors) {
let dist = new Array(n).fill(-1);
dist[0] = 0;
let q = [0];
while (q.length > 0) {
let x = q.shift();
for (let y of neighbors[x]) {
if (dist[y] >= 0) {
continue;
}
q.push(y);
dist[y] = dist[x] + 1;
}
}
return dist[n - 1];
};
// dp
var shortestDistanceAfterQueries2 = function(n, queries) {
let prev = new Array(n).fill().map(() => []);
for (let i = 1; i < n; i++) {
prev[i].push(i - 1);
}
let dp = new Array(n).fill(0).map((_, i) => i);
let res = new Array(queries.length);
for (let i = 0; i < queries.length; i++) {
prev[queries[i][1]].push(queries[i][0]);
for (let v = queries[i][1]; v < n; v++) {
for (let u of prev[v]) {
dp[v] = Math.min(dp[v], dp[u] + 1);
}
}
res[i] = dp[n - 1];
}
return res;
};
use std::collections::VecDeque;
impl Solution {
pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut neighbors: Vec<Vec<i32>> = vec![Vec::new(); n as usize];
for i in 0..n-1 {
neighbors[i as usize].push(i + 1);
}
let mut res: Vec<i32> = Vec::new();
for query in queries {
neighbors[query[0] as usize].push(query[1]);
res.push(Self::bfs(n as usize, &neighbors));
}
res
}
fn bfs(n: usize, neighbors: &Vec<Vec<i32>>) -> i32 {
let mut dist = vec![-1; n];
let mut q = VecDeque::new();
q.push_back(0);
dist[0] = 0;
while let Some(x) = q.pop_front() {
for &y in &neighbors[x] {
if dist[y as usize] >= 0 {
continue;
}
q.push_back(y as usize);
dist[y as usize] = dist[x] + 1;
}
}
dist[n - 1]
}
}
impl Solution {
// dp
pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut prev: Vec<Vec<i32>> = vec![Vec::new(); n as usize];
let mut dp: Vec<i32> = vec![0; n as usize];
for i in 1..n {
prev[i as usize].push(i - 1);
dp[i as usize] = i;
}
let mut res: Vec<i32> = Vec::new();
for query in queries {
prev[query[1] as usize].push(query[0]);
for v in query[1] as usize..n as usize {
for &u in &prev[v] {
dp[v] = dp[v].min(dp[u as usize] + 1);
}
}
res.push(dp[(n - 1) as usize]);
}
res
}
}
func shortestDistanceAfterQueries(n int, queries [][]int) []int {
from := make([][]int, n)
f := make([]int, n)
for i := 1; i < n; i++ {
f[i] = i
}
ans := make([]int, len(queries))
for qi, q := range queries {
l, r := q[0], q[1]
from[r] = append(from[r], l)
if f[l]+1 < f[r] {
f[r] = f[l] + 1
for i := r + 1; i < n; i++ {
f[i] = min(f[i], f[i-1]+1)
for _, j := range from[i] {
f[i] = min(f[i], f[j]+1)
}
}
}
ans[qi] = f[n-1]
}
return ans
}
// bfs
func shortestDistanceAfterQueries2(n int, queries [][]int) []int {
g := make([][]int, n-1)
for i := range g {
g[i] = append(g[i], i+1)
}
vis := make([]int, n-1)
bfs := func(i int) int {
q := []int{0}
for step := 1; ; step++ {
tmp := q
q = nil
for _, x := range tmp {
for _, y := range g[x] {
if y == n-1 {
return step
}
if vis[y] != i {
vis[y] = i
q = append(q, y)
}
}
}
}
}
ans := make([]int, len(queries))
for i, q := range queries {
g[q[0]] = append(g[q[0]], q[1])
ans[i] = bfs(i + 1)
}
return ans
}
class Solution:
# bfs
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
g = [[i + 1] for i in range(n - 1)]
vis = [-1] * (n - 1)
def bfs(i: int) -> int:
q = deque([0])
for step in count(1):
tmp = q
q = []
for x in tmp:
for y in g[x]:
if y == n - 1:
return step
if vis[y] != i:
vis[y] = i
q.append(y)
return -1
ans = [0] * len(queries)
for i, (l, r) in enumerate(queries):
g[l].append(r)
ans[i] = bfs(i)
return ans
# dp
def shortestDistanceAfterQueries2(self, n: int, queries: List[List[int]]) -> List[int]:
frm = [[] for _ in range(n)]
f = list(range(n))
ans = []
for l, r in queries:
frm[r].append(l)
if f[l] + 1 < f[r]:
f[r] = f[l] + 1
for i in range(r + 1, n):
f[i] = min(f[i], f[i - 1] + 1, min((f[j] for j in frm[i]), default=inf) + 1)
ans.append(f[-1])
return ans
class Solution {
// dp
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
List<Integer>[] from = new ArrayList[n];
Arrays.setAll(from, i -> new ArrayList<>());
int[] f = new int[n];
for (int i = 1; i < n; i++) {
f[i] = i;
}
int[] ans = new int[queries.length];
for (int qi = 0; qi < queries.length; qi++) {
int l = queries[qi][0];
int r = queries[qi][1];
from[r].add(l);
if (f[l] + 1 < f[r]) {
f[r] = f[l] + 1;
for (int i = r + 1; i < n; i++) {
f[i] = Math.min(f[i], f[i - 1] + 1);
for (int j : from[i]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
ans[qi] = f[n - 1];
}
return ans;
}
// bfs
public int[] shortestDistanceAfterQueries2(int n, int[][] queries) {
List<Integer>[] g = new ArrayList[n - 1];
Arrays.setAll(g, i -> new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
g[i].add(i + 1);
}
int[] ans = new int[queries.length];
int[] vis = new int[n - 1];
for (int i = 0; i < queries.length; i++) {
g[queries[i][0]].add(queries[i][1]);
ans[i] = bfs(i + 1, g, vis, n);
}
return ans;
}
private int bfs(int i, List<Integer>[] g, int[] vis, int n) {
List<Integer> q = new ArrayList<>();
q.add(0);
for (int step = 1; ; step++) {
List<Integer> tmp = q;
q = new ArrayList<>();
for (int x : tmp) {
for (int y : g[x]) {
if (y == n - 1) {
return step;
}
if (vis[y] != i) {
vis[y] = i;
q.add(y);
}
}
}
}
}
}
