day 62 第十一章：图论part11 Floyd 算法精讲 A * 算法精讲 （A star算法）
使命日期：8.6题目一链接：97. 小明逛公园 (kamacoder.com)
思路：
在这之前我们讲解过，dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA） 都是单源最短路，即只能有一个起点。
而本题是多源最短路，即 求多个起点到多个终点的多条最短路径。
代码：
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));// 因为边的最大距离是10^4
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid = val;
grid = val; // 注意这里是双向图
}
// 开始 floyd
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grid = min(grid, grid + grid);
}
}
}
// 输出结果
int z, start, end;
cin >> z;
while (z--) {
cin >> start >> end;
if (grid == 10005) cout << -1 << endl;
else cout << grid << endl;
}
}
难点：
解释细节1：
题目二链接：
思路：
代码：
难点：
解释细节1：
题目三链接：
思路：
代码：
难点：
解释细节1：
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]