Shortest Distance After Road Addition Queries I solution and explanation

from collections import deque

def shortest_path(n, queries):
    # Initialize graph with the default path 0 -> 1 -> ... -> n-1
    graph = {i: [i + 1] for i in range(n - 1)}
    graph[n-1] = []
    
    def bfs_distance(start, end):
        visited = [False] * n
        queue = deque([(start, 0)])
        visited[start] = True
        while queue:
            node, dist = queue.popleft()
            if node == end:
                return dist
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append((neighbor, dist + 1))
        return -1  # If unreachable (should not happen)
    
    answers = []
    for u, v in queries:
        graph[u].append(v)
        answers.append(bfs_distance(0, n - 1))
    return answers

# Example usage
n = 5
queries = [[2, 4], [0, 2], [0, 4]]
print(shortest_path(n, queries))

function shortestPath(n, queries) {
  const graph = Array.from({ length: n }, () => []);
  for (let i = 0; i < n - 1; ++i) {
    graph[i].push(i + 1);
  }

  function bfsDistance(start, end) {
    let queue = [{ node: start, dist: 0 }];
    let visited = Array(n).fill(false);
    visited[start] = true;

    for (let position = 0; position < queue.length; position++) {
      const { node, dist } = queue[position];

      if (node === end) return dist;

      for (const neighbor of graph[node]) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push({ node: neighbor, dist: dist + 1 });
        }
      }
    }
    return -1;
  }

  let results = [];
  for (const [u, v] of queries) {
    graph[u].push(v);
    results.push(bfsDistance(0, n - 1));
  }
  return results;
}

// Example usage
const n = 5;
const queries = [[2, 4], [0, 2], [0, 4]];
console.log(shortestPath(n, queries));

import java.util.*;

public class ShortestPath {
    public static List<Integer> shortestPath(int n, List<int[]> queries) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            if (i < n - 1) {
                graph.get(i).add(new int[]{i + 1, 1});
            }
        }

        List<Integer> results = new ArrayList<>();

        for (int[] query : queries) {
            int u = query[0], v = query[1];
            graph.get(u).add(new int[]{v, 1});
            results.add(dijkstra(n, graph));
        }

        return results;
    }

    private static int dijkstra(int n, List<List<int[]>> graph) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0], d = current[1];

            if (d > dist[u]) continue;

            for (int[] edge : graph.get(u)) {
                int v = edge[0], weight = edge[1];
                if (d + weight < dist[v]) {
                    dist[v] = d + weight;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }

        return dist[n - 1];
    }

    public static void main(String[] args) {
        int n = 5;
        List<int[]> queries = Arrays.asList(new int[]{2, 4}, new int[]{0, 2}, new int[]{0, 4});
        System.out.println(shortestPath(n, queries));
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

vector<int> shortestPath(int n, vector<pair<int, int>>& queries) {
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        graph[i].emplace_back(i + 1, 1);
    }

    auto dijkstra = [&](int target) {
        vector<int> dist(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        dist[0] = 0;
        pq.emplace(0, 0);

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;

            for (auto& [v, weight] : graph[u]) {
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.emplace(dist[v], v);
                }
            }
        }
        return dist[target];
    };

    vector<int> results;
    for (auto& [u, v] : queries) {
        graph[u].emplace_back(v, 1);
        results.push_back(dijkstra(n - 1));
    }
    return results;
}

int main() {
    int n = 5;
    vector<pair<int, int>> queries = {{2, 4}, {0, 2}, {0, 4}};
    vector<int> answer = shortestPath(n, queries);
    for (int res : answer) {
        cout << res << " ";
    }
    return 0;
}

function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < n - 1; ++i) {
        g[i].push(i + 1);
    }
    const bfs = (i: number): number => {
        const q: number[] = [i];
        const vis: boolean[] = Array(n).fill(false);
        vis[i] = true;
        for (let d = 0; ; ++d) {
            const nq: number[] = [];
            for (const u of q) {
                if (u === n - 1) {
                    return d;
                }
                for (const v of g[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        nq.push(v);
                    }
                }
            }
            q.splice(0, q.length, ...nq);
        }
    };
    const ans: number[] = [];
    for (const [u, v] of queries) {
        g[u].push(v);
        ans.push(bfs(0));
    }
    return ans;
}

func shortestDistanceAfterQueries(n int, queries [][]int) []int {
	g := make([][]int, n)
	for i := range g {
		g[i] = append(g[i], i+1)
	}
	bfs := func(i int) int {
		q := []int{i}
		vis := make([]bool, n)
		vis[i] = true
		for d := 0; ; d++ {
			for k := len(q); k > 0; k-- {
				u := q[0]
				if u == n-1 {
					return d
				}
				q = q[1:]
				for _, v := range g[u] {
					if !vis[v] {
						vis[v] = true
						q = append(q, v)
					}
				}
			}
		}
	}
	ans := make([]int, len(queries))
	for i, q := range queries {
		g[q[0]] = append(g[q[0]], q[1])
		ans[i] = bfs(0)
	}
	return ans
}