Сегодня мы решаем задачу 3243. Shortest Distance After Road Addition Queries I
Постановка
В задаче требуется вычислить кратчайший путь от города 0 до города n-1 после каждой из последовательных добавлений новых дорог в граф. Изначально города соединены цепочкой дорог, и после каждой операции добавляется новая односторонняя дорога между двумя городами. Необходимо после каждой операции находить кратчайшее расстояние от города 0 до города n-1.
🔍 Идея
Данное решение использует оптимизированный подход с поочередным обновлением расстояний с помощью BFS и ранним выходом при нахождении цели (города n-1). Мы обновляем граф и расстояния только при необходимости, что позволяет сократить количество ненужных вычислений и повысить производительность.
📚 Обзор решения
-
Инициализация графа и расстояний:
- Сначала создаем список смежности
succ, который представляет дороги между городами, инициализируем его так, чтобы города были соединены цепочкой (каждый город соединен с следующим).
- Массив
dist инициализируется так, что расстояние от города 0 до города i равно i (для начальной цепочки).
-
Обработка запросов:
- Для каждого запроса добавляется новая дорога между городами
u и v. После этого запускается BFS с города v для обновления кратчайших расстояний до всех достижимых городов.
-
Ранний выход в BFS:
BFS прекращается, как только мы достигаем города n-1, чтобы избежать ненужных вычислений, если путь уже найден.
-
Результат:
После обработки каждого запроса мы добавляем текущую длину кратчайшего пути от города 0 до города n-1 в массив ответов.
⏳ Сложность
- Время: Каждый запрос требует выполнения BFS, что в худшем случае занимает
O(V+E),
где V — количество городов, а E — количество дорог.
Таким образом, общая сложность для всех запросов: O(Q×(V+E)), где Q — количество запросов.
- Память: Мы используем
O(V+E) для хранения списка смежности и массива расстояний, а также очереди BFS.
Исходный код решения
impl Solution {
pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
// Initialize graph adjacency list
let mut succ: Vec<_> = (0..n-1).map(|i| vec![i+1]).collect();
// Initialize distances directly for the initial chain
let mut dist: Vec<i32> = (0..n as i32).collect();
// Result vector
let mut ans = Vec::new();
// Create the queue once, before the loop
let mut queue = std::collections::VecDeque::new();
// Process each query incrementally
for query in queries {
let (u, v) = (query[0] as usize, query[1] as usize);
succ[u].push(v); // Add new road
// Initialize updated flag inline
let updated = if dist[v] > dist[u] + 1 {
dist[v] = dist[u] + 1;
queue.clear(); // Clear the queue since we're stopping early
queue.push_back((v as i32, dist[v])); // Push both node and its distance
true
} else {
false
};
// Perform BFS only if necessary
if updated {
while let Some((curr, curr_dist)) = queue.pop_front() {
let curr = curr as usize; // Convert back to `usize` for graph indexing
if curr == n - 1 {
break; // Early exit if the destination is reached
}
// Process neighbors, compare and push updated distances
for &neighbor in &succ[curr] {
let new_dist = curr_dist + 1;
if dist[neighbor] > new_dist {
dist[neighbor] = new_dist;
queue.push_back((neighbor as i32, new_dist)); // Pass the updated distance along
}
}
}
}
// Record the shortest path to city n-1
ans.push(dist[n - 1]);
}
ans
}