ToB企服应用市场:ToB评测及商务社交产业平台

标题: day 62 第十一章：图论part11 Floyd 算法精讲 A * 算法精讲 （A star算法） [打印本页]

---

作者: 美丽的神话    时间: 2024-8-14 00:57
标题: day 62 第十一章：图论part11 Floyd 算法精讲 A * 算法精讲 （A star算法）
使命日期：8.6
题目一链接：97. 小明逛公园 (kamacoder.com)
思路：
在这之前我们讲解过，dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA） 都是单源最短路，即只能有一个起点。
而本题是多源最短路，即 求多个起点到多个终点的多条最短路径。
代码：

1. #include <iostream>
2. #include <vector>
3. #include <list>
4. using namespace std;
6. int main() {
7.     int n, m, p1, p2, val;
8.     cin >> n >> m;
10.     vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // 因为边的最大距离是10^4
11.     for(int i = 0; i < m; i++){
12.         cin >> p1 >> p2 >> val;
13.         grid[p1][p2][0] = val;
14.         grid[p2][p1][0] = val; // 注意这里是双向图
16.     }
17.     // 开始 floyd
18.     for (int k = 1; k <= n; k++) {
19.         for (int i = 1; i <= n; i++) {
20.             for (int j = 1; j <= n; j++) {
21.                 grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
22.             }
23.         }
24.     }
25.     // 输出结果
26.     int z, start, end;
27.     cin >> z;
28.     while (z--) {
29.         cin >> start >> end;
30.         if (grid[start][end][n] == 10005) cout << -1 << endl;
31.         else cout << grid[start][end][n] << endl;
32.     }
33. }

复制代码

难点：
解释细节1：

---

---

---

题目二链接：
思路：
代码：
难点：
解释细节1：

---

---

---

题目三链接：
思路：
代码：
难点：
解释细节1：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4