哪个做h5的网站好用,建筑公司企业愿景平台,建立可以在线做照片的网站,做网站投注代理犯罪吗Floyd 算法#xff08;求多源汇最短路#xff09;
题目链接#xff1a;97. 小明逛公园
题目描述#xff1a;
小明喜欢去公园散步#xff0c;公园内布置了许多的景点#xff0c;相互之间通过小路连接#xff0c;小明希望在观看景点的同时#xff0c;能够节省体力求多源汇最短路
题目链接97. 小明逛公园
题目描述
小明喜欢去公园散步公园内布置了许多的景点相互之间通过小路连接小明希望在观看景点的同时能够节省体力走最短的路径。
给定一个公园景点图图中有 N 个景点编号为 1 到 N以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。
小明有 Q 个观景计划每个计划都有一个起点 start 和一个终点 end表示他想从景点 start 前往景点 end。由于小明希望节省体力他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。
算法思想 使用三重for循环遍历从1~n节点grip二维数组含义是表示点i和j间的距离将其初始化为INT_MAX对角线初始化为0。使用grip[i][j] min(grip[i][j],grip[i][k]grip[k][j])来判断最短路径。 代码
#includeiostream
#includevector
#includeclimits
using namespace std;void floyd(vectorvectorint graphs)
{int n graphs.size() - 1;for(int k 1; k n; k)for(int i 1; i n; i)for(int j 1; j n; j)if(graphs[i][k] ! INT_MAX graphs[k][j] ! INT_MAX)graphs[i][j] min(graphs[i][j],graphs[i][k] graphs[k][j]);
}int main()
{int n,m;cin n m;vectorvectorint graphs(n1,vectorint(n1,INT_MAX));for(int i 1; i n; i) graphs[i][i] 0;for(int i 0; i m; i){int u,v,w;cin u v w;graphs[u][v] min(graphs[u][v],w);graphs[v][u] min(graphs[v][u],w);}floyd(graphs);int q;cin q;while(q--){int start,end;cin start end;if(graphs[start][end] INT_MAX) cout -1 endl;else cout graphs[start][end] endl;}return 0;
}
A*算法
题目链接127. 骑士的攻击
题目描述
在象棋中马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标要求根据骑士的移动规则计算从起点到达目标点所需的最短步数。
棋盘大小 1000 x 1000棋盘的 x 和 y 坐标均在 [1, 1000] 区间内包含边界
算法思想 1、该算法是对宽搜算法的优化能保证有方向地去搜索点。在宽搜基础上增添了权重概念。 2、如何保证有方向搜索--对每一个点设置一个权重ffghg表示起点达到目前遍历节点的距离h表示目前遍历的节点到达终点的距离。距离计算公式如下 曼哈顿距离计算方式 d abs(x1-x2)abs(y1-y2)欧氏距离常用不会超时 计算方式d (x1-x2)^2 (y1-y2)^2 切比雪夫距离计算方式d max(abs(x1 - x2), abs(y1 - y2)) 3、每次使用具有最小权重的点来更新节点位置---使用优先级队列保存 代码
#includeiostream
#includevector
#includequeue
#includealgorithm
using namespace std;int b1,b2;
int dx[8] {-1,-1,1,1,2,2,-2,-2};
int dy[8] {2,-2,2,-2,-1,1,-1,1};typedef struct Knight
{int a1,a2;int f,g,h;bool operator (const struct Knight k) const{return k.f f;}
}Knight;int function(const Knight knt)
{return (knt.a1 - b1)*(knt.a1 - b1) (knt.a2 - b2)*(knt.a2 - b2);
}void Astar(vectorvectorint step, const Knight knt, priority_queueKnight pq)
{Knight cur,next;while(!pq.empty()){cur pq.top(),pq.pop();if(cur.a1 b1 cur.a2 b2) break;for(int i 0; i 8; i){next.a1 cur.a1 dx[i];next.a2 cur.a2 dy[i];if(next.a1 1 || next.a1 1000 || next.a2 1 || next.a2 1000) continue;if(!step[next.a1][next.a2]){step[next.a1][next.a2] step[cur.a1][cur.a2] 1;next.g cur.g 5;next.h function(next);next.f next.g next.h;pq.push(next);}}}
}int main()
{int a1,a2,n;cin n;while(n--){priority_queueKnight pq;vectorvectorint step(1010,vectorint(1010));cin a1 a2 b1 b2;Knight knt;knt.a1 a1;knt.a2 a2;knt.g 0;knt.h function(knt);knt.f knt.g knt.h;pq.push(knt);Astar(step,knt,pq);cout step[b1][b2] endl;}return 0;
}
