题目:
给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市,编号从 0 到 n - 1。初始时,每个城市 i 都有一条单向道路通往城市 i + 1( 0 <= i < n - 1)。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后,你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer,对于范围 [0, queries.length - 1] 中的每个 i,answer[i] 是处理完前 i +1 个查询后,从城市 0 到城市 n - 1 的最短路径的长度。
1. 题目重述及关键字提取
题目重述:
给定一个整数 n
和一个二维整数数组 queries
,表示有 n
个城市,城市编号从 0
到 n - 1
。每个城市 i
有一条单向道路通往城市 i + 1
。对于每个查询 queries[i] = [ui, vi]
,意味着新建一条从城市 ui
到城市 vi
的单向道路。每次查询后,需要计算从城市 0
到城市 n - 1
的最短路径长度,并返回这些长度的数组。
关键字提取:
- 城市 (
cities
) - 单向道路 (
directed roads
) - 最短路径 (
shortest path
) - 查询 (
queries
) - 数组结果 (
result array
)
2. 解题思路与分析
方法一:广度优先遍历 (BFS)
思路:
广度优先搜索是解决最短路径问题的有效方式,尤其是在图的边权均为 1 的情况下(每条边的权重相同)。首先,构建一个图结构来表示城市和道路,然后从城市 0
开始进行 BFS,记录到每个城市的最短距离。
步骤:
- 初始化一个图的邻接表。
- 将初始的单向道路添加到图中。
- 对于每个查询,将新道路添加到图中。
- 使用 BFS 从城市
0
开始,寻找最短路径到城市n - 1
。 - 返回每一步的最短路径长度。
C++代码(广度优先搜索)
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {unordered_map<int, vector<int>> graph;// Initialize the graph with initial roadsfor (int i = 0; i < n - 1; ++i) {graph[i].push_back(i + 1);}vector<int> answer;for (auto& query : queries) {int u = query[0], v = query[1];graph[u].push_back(v); // Add the new road// BFS to find the shortest path from 0 to n-1vector<int> dist(n, -1);dist[0] = 0;queue<int> q;q.push(0);while (!q.empty()) {int node = q.front(); q.pop();for (int neighbor : graph[node]) {if (dist[neighbor] == -1) { // Not visiteddist[neighbor] = dist[node] + 1;q.push(neighbor);}}}answer.push_back(dist[n - 1]);}return answer;
}
Java代码(广度优先搜索)
public class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {Map<Integer, List<Integer>> graph = new HashMap<>();// Initialize the graph with initial roadsfor (int i = 0; i < n - 1; i++) {graph.putIfAbsent(i, new ArrayList<>());graph.get(i).add(i + 1);}int[] answer = new int[queries.length];for (int i = 0; i < queries.length; i++) {int u = queries[i][0], v = queries[i][1];graph.putIfAbsent(u, new ArrayList<>());graph.get(u).add(v); // Add the new road// BFS to find the shortest path from 0 to n-1int[] dist = new int[n];Arrays.fill(dist, -1);dist[0] = 0;Queue<Integer> queue = new LinkedList<>();queue.add(0);while (!queue.isEmpty()) {int node = queue.poll();for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {if (dist[neighbor] == -1) { // Not visiteddist[neighbor] = dist[node] + 1;queue.add(neighbor);}}}answer[i] = dist[n - 1];}return answer;}
}
方法二:动态规划 (Dynamic Programming)
思路:
在动态规划中,我们维护一个数组 dp
,dp[i]
表示从城市 0
到城市 i
的最短距离。初始时,起点城市 0
的距离设置为 0
,其他城市的距离设置为无穷大(表示尚未到达)。通过逐步处理每个查询,我们可以利用新添加的道路更新各个城市的最短距离。
步骤:
-
初始化
dp
数组:- 创建一个大小为
n
的数组dp
,初始化为无穷大(numeric_limits<int>::max()
)。 - 设置
dp[0] = 0
,表示从城市0
到自身的距离为0
。
- 创建一个大小为
-
初始化前驱信息:
- 为了便于后续更新,维护一个二维数组
prev
,prev[i]
存储所有可以到达城市i
的前驱城市。 - 对于每个城市
i
(从1
到n-1
),将城市i-1
添加为它的前驱,并初始设置dp[i] = i
,这代表最坏情况下通过i-1
次到达城市i
。
- 为了便于后续更新,维护一个二维数组
-
处理每个查询:
- 对于每个查询
[u, v]
,将城市u
添加到城市v
的前驱列表prev[v]
中,表示新建了从u
到v
的单向道路。
- 对于每个查询
-
状态转移:
- 从城市
v
开始,遍历城市w
(从v
到n-1
),对于每个城市w
,检查其所有前驱城市u
(从prev[w]
中获取)。 - 通过公式
dp[w] = min(dp[w], dp[u] + 1)
更新城市w
的最短距离。此步骤确保在新道路添加后,所有通过该新道路可到达的城市的最短路径都得到更新。
- 从城市
-
记录结果:
- 在处理完每个查询后,将当前城市
n-1
的最短距离dp[n - 1]
添加到结果数组res
中。如果dp[n - 1]
仍然为无穷大,表示不可达,返回-1
。
- 在处理完每个查询后,将当前城市
-
返回结果:
- 返回所有查询的结果数组
res
,其中每一项表示在当前查询后从城市0
到城市n - 1
的最短距离。
- 返回所有查询的结果数组
C++代码(动态规划)
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries) { vector<vector<int>> prev(n); vector<int> dp(n, numeric_limits<int>::max()); // 使用无穷大进行初始化 dp[0] = 0; // 起点到自身的距离为0 // 初始填充前驱信息 for (int i = 1; i < n; i++) { prev[i].push_back(i - 1); dp[i] = i; // 最坏情况是 n-1 步到达 i } vector<int> res; // 处理每个查询 for (auto &query : queries) { int u = query[0], v = query[1]; prev[v].push_back(u); // 更新前驱 // 状态转移 for (int w = v; w < n; w++) { for (int u : prev[w]) { dp[w] = min(dp[w], dp[u] + 1); } } // 记录到最后一座城市的距离 res.push_back(dp[n - 1] != numeric_limits<int>::max() ? dp[n - 1] : -1); } return res; }
Java代码(动态规划)
public int[] shortestDistanceAfterQueries(int n, int[][] queries) { List<List<Integer>> prev = new ArrayList<>(); for (int i = 0; i < n; i++) { prev.add(new ArrayList<>()); } int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); // 使用无穷大进行初始化 dp[0] = 0; // 起点到自身的距离为0 // 初始填充前驱信息 for (int i = 1; i < n; i++) { prev.get(i).add(i - 1); dp[i] = i; // 最坏情况是 n-1 步到达 i } int[] res = new int[queries.length]; // 处理每个查询 for (int i = 0; i < queries.length; i++) { int u = queries[i][0], v = queries[i][1]; prev.get(v).add(u); // 更新前驱 // 状态转移 for (int w = v; w < n; w++) { for (int j : prev.get(w)) { dp[w] = Math.min(dp[w], dp[j] + 1); } } // 记录到最后一座城市的距离 res[i] = dp[n - 1] != Integer.MAX_VALUE ? dp[n - 1] : -1; } return res; }
3. 总结分析
广度优先遍历 (BFS) 与动态规划 (Dynamic Programming):
-
广度优先遍历:
- BFS 适用于图的最短路径问题,尤其是所有边的权值相同的情况。通过逐层遍历,可以有效找到从起点到终点的最短路径。
-
动态规划:
- 动态规划适合在路径长度需要动态更新的情况下,通过不断维护到达每个节点的最小路径,还可以在每次查询后直接更新结果。