学习资料：代码随想录
Floyd 算法精讲
卡码网：97. 小明逛公园
首先明确floyd算法解决的是多源最短路径问题，对边的权的正负值没有要求，而且是动态规划的思想
五部曲：
定义：grid[i][j][k]表示从i出发到j经过[1...k]中某一个节点的最短距离
递推：1、节点i 到 节点j 的最短路径经过节点k，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]（i到k不经过k+k到j不经过k）
2、节点i 到 节点j 的最短路径不经过节点k，grid[i][j][k] = grid[i][j][k - 1]
取一个最小值：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])
为什么最后一位是k-1呢，其实模拟一遍是最清楚的，个人浅显地认为，简要来说，还是动态规划中递推的思想：
假设你有节点 1~5，现在计算 grid[1][4][3]
-
意思是：你正在计算 从 1 到 4 的最短路径，中间节点只能是 编号 ≤ 3 的点
所以这里你根本还不能用点 4 和点 5，它们 大于 k=3，不在当前阶段允许的中间节点集合内。
用点4和点5是递推到后面的事
初始化：i到j不经过节点的时候，即grid[i][j][0]，可以通过输入就初始化了，其他值要给一个比10^4大的值，因为递推的过程是取小值；也不能太大，后面还要加，怕溢出。
遍历顺序：根据递推公式，得到grid[i][j][k]需要用到grid[i][k][k - 1]，grid[k][j][k - 1] ，grid[i][j][k - 1]，故吧k放在最外层
打印：略
//五部曲
//定义
//递推公式
//初始化
//遍历顺序
//打印
#include <iostream>
#include <vector>
using namespace std;int main(){int n,m,u,v,w,q,start,end;cin>>n>>m;vector<vector<vector<int>>> roads(n+1,vector<vector<int>>(n+1,vector<int>(n+1,10005)));for(int i=0;i<m;i++){cin>>u>>v>>w;roads[u][v][0]=w; //初始化roads[v][u][0]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){roads[i][j][k]=min(roads[i][j][k-1],roads[i][k][k-1]+roads[k][j][k-1]); //不经过k点和经过k点}}}cin>>q;while(q--){cin>>start>>end;if(roads[start][end][n]==10005) cout<<-1<<endl;else{cout<<roads[start][end][n]<<endl;}}
}可以把空间复杂度压缩到O(n^2)
//五部曲
//定义
//递推公式
//初始化
//遍历顺序
//打印
#include <iostream>
#include <vector>
using namespace std;int main(){int n,m,u,v,w,q,start,end;cin>>n>>m;vector<vector<int>> roads(n+1,vector<int>(n+1,10005));for(int i=0;i<m;i++){cin>>u>>v>>w;roads[u][v]=w; //初始化roads[v][u]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){roads[i][j]=min(roads[i][j],roads[i][k]+roads[k][j]); //不经过k点和经过k点}}}cin>>q;while(q--){cin>>start>>end;if(roads[start][end]==10005) cout<<-1<<endl;else{cout<<roads[start][end]<<endl;}}
}A * 算法精讲 （A star算法）
卡码网：126. 骑士的攻击
该说不说这道题的题目描述晃到我的，上来说马走日，象飞田，结果题目是求骑士的最少步数。
A*算法其实还是广度优先搜索，不过加上了启发式函数，启发式函数算的是从起点到终点并经过当前点要走的距离。
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;int moves[1001][1001];
int dir[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};
int b1,b2;struct knight{int x,y; // 当前坐标int g,h,f; // g=走过的代价，h=预估代价（启发式函数），f=g+hbool operator < (const knight& k) const{ //这是一个成员函数，重载了 < 运算符。//operator <：表示重载“小于”运算符//(const Knight &k)：要和另一个 Knight 对象 k 进行比较//const：表示这个函数不会修改当前对象的成员变量//返回值是 bool，表示当前对象是否 小于 参数 kreturn k.f<f; // 小顶堆，f 越小优先级越高}
};priority_queue<knight> que;
int Heuristic(const knight& k){return (k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2); //启发函数采用的是 欧几里得距离的平方（不开根号），因为这样避免了浮点计算，提高精度与效率
}void astar(const knight& k){ //输入起点 k，然后开始扩展knight cur,next; que.push(k); // 起点进队while(!que.empty()){cur = que.top(); que.pop(); //每次从堆里取出 f 最小的节点if(cur.x==b1&&cur.y==b2){ //终点判断break;}for(int i=0;i<8;i++){ //尝试扩展8个方向next.x = cur.x+dir[i][0];next.y = cur.y+dir[i][1];if(next.x<1||next.y>1000||next.y<1||next.y>1000){ //越界检查continue;}if(!moves[next.x][next.y]){ //没访问过,更新状态并入队moves[next.x][next.y]=moves[cur.x][cur.y]+1;next.g=cur.g+5; // 因为一步是 √5，不开根next.h=Heuristic(next);next.f=next.g+next.h;que.push(next);}}}
}int main(){int n,a1,a2;cin>>n;while(n--){cin>>a1>>a2>>b1>>b2;memset(moves,0,sizeof(moves));knight start;start.x=a1;start.y=a2;start.g=0;start.h=Heuristic(start);start.f=start.g+start.h;astar(start);while(!que.empty()){ //多组输入，清空 moves 数组que.pop();}cout<<moves[b1][b2]<<endl;}return 0;
}对于这个重载语法，作用是为了让 priority_queue 成为小顶堆 —— 也就是 f 越小，优先级越高。priority_queue 默认是 大顶堆，它把“最大的”元素放在堆顶。所以你必须让“小的 f 看起来是“更大”的”，于是写成：return k.f < f;
priority_queue 会把 “operator < 为 true 的对象” 排在后面。
还可用lambda：
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;int moves[1001][1001];
int dir[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};
int b1,b2;struct knight{int x,y; // 当前坐标int g,h,f; // g=走过的代价，h=预估代价（启发式函数），f=g+h// bool operator < (const knight& k) const{ //这是一个成员函数，重载了 < 运算符。// //operator <：表示重载“小于”运算符// //(const Knight &k)：要和另一个 Knight 对象 k 进行比较// //const：表示这个函数不会修改当前对象的成员变量// //返回值是 bool，表示当前对象是否 小于 参数 k// return k.f<f; // 小顶堆，f 越小优先级越高// }
};//priority_queue<knight> que;
int Heuristic(const knight& k){return (k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2); //启发函数采用的是 欧几里得距离的平方（不开根号），因为这样避免了浮点计算，提高精度与效率
}void astar(const knight& k){ //输入起点 k，然后开始扩展auto cmp = [](const knight& a, const knight& b) {return a.f > b.f; // f 小的优先};priority_queue<knight, vector<knight>, decltype(cmp)> que(cmp);knight cur,next; que.push(k); // 起点进队while(!que.empty()){cur = que.top(); que.pop(); //每次从堆里取出 f 最小的节点if(cur.x==b1&&cur.y==b2){ //终点判断break;}for(int i=0;i<8;i++){ //尝试扩展8个方向next.x = cur.x+dir[i][0];next.y = cur.y+dir[i][1];if(next.x<1||next.y>1000||next.y<1||next.y>1000){ //越界检查continue;}if(!moves[next.x][next.y]){ //没访问过,更新状态并入队moves[next.x][next.y]=moves[cur.x][cur.y]+1;next.g=cur.g+5; // 因为一步是 √5，不开根next.h=Heuristic(next);next.f=next.g+next.h;que.push(next);}}}
}int main(){int n,a1,a2;cin>>n;while(n--){cin>>a1>>a2>>b1>>b2;memset(moves,0,sizeof(moves));knight start;start.x=a1;start.y=a2;start.g=0;start.h=Heuristic(start);start.f=start.g+start.h;astar(start);// while(!que.empty()){ //多组输入，清空 moves 数组// que.pop();// }cout<<moves[b1][b2]<<endl;}return 0;
}A * 算法并不能保证一定是最短路，虽然本题求出来是最短路
memset函数：C 库函数 – memset() | 菜鸟教程
重载运算符：C++ 重载运算符和重载函数 | 菜鸟教程
lambda：C++ 函数 | 菜鸟教程
给陪伴我的网易云歌单也做个笔记：网易云音乐
音乐确实承载着太多回忆，可能将来的某一天，听到热河的前奏响起，闭上眼就会回到冬天坐在电脑前的那个晚上
_百度推广优化方案_郑州官网网络营销外包)
