3243. Shortest Distance After Road Addition Queries I Medium

1/**
2 * [3243] Shortest Distance After Road Addition Queries I
3 *
4 * You are given an integer n and a 2D integer array queries.
5 * 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.
6 * 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.
7 * 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.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">n = 5, queries = [[2,4],[0,2],[0,4]]</span>
12 * Output: <span class="example-io">[3,2,1]</span>
13 * Explanation: 
14 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image8.jpg" style="width: 350px; height: 60px;" />
15 * After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
16 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image9.jpg" style="width: 350px; height: 60px;" />
17 * After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
18 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image10.jpg" style="width: 350px; height: 96px;" />
19 * After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">n = 4, queries = [[0,3],[0,2]]</span>
24 * Output: <span class="example-io">[1,1]</span>
25 * Explanation:
26 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image11.jpg" style="width: 300px; height: 70px;" />
27 * After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
28 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image12.jpg" style="width: 300px; height: 70px;" />
29 * After the addition of the road from 0 to 2, the length of the shortest path remains 1.
30 * </div>
31 *  
32 * Constraints:
33 * 
34 * 	3 <= n <= 500
35 * 	1 <= queries.length <= 500
36 * 	queries[i].length == 2
37 * 	0 <= queries[i][0] < queries[i][1] < n
38 * 	1 < queries[i][1] - queries[i][0]
39 * 	There are no repeated roads among the queries.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/
45// discuss: https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
51        vec![]
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3243() {
63    }
64}
65