织梦网站数据库备份文件夹,wordpress 单一商品主题,水果商城的设计与实现,深圳关键词优化报价Dijkstra算法核心总结#xff1a; 求解 单源最短路径问题#xff08;给定一个起点#xff0c;求它到所有其他节点的最短距离#xff09;#xff0c;仅适用于 边权非负 的图。 2. 核心思想 贪心策略#xff1a;每次选 “当前离起点最近的未处理节点”#xff0c;以它为…Dijkstra算法核心总结求解单源最短路径问题给定一个起点求它到所有其他节点的最短距离仅适用于边权非负的图。2. 核心思想贪心策略每次选 “当前离起点最近的未处理节点”以它为中介更新邻接节点的最短距离优先队列优化用堆快速找到 “最近节点”时间复杂度从 O (n²) 降到 O (m log n)n 节点数m 边数松弛操作对于边 u→v若d[v] d[u] w则更新d[v]核心操作所有最短路径算法的基础。3. 邻接表核心逻辑e[a]是节点 a 的 “出边清单”push_back({b,c})就是给清单加一条 “a→b权重 c” 的边遍历e[u]就是把节点 u 的所有出边都拿出来处理。类似于 后面还拉着一些边4.个必记关键易忘点堆的技巧优先队列默认是大根堆存-d[v]才能优先处理距离小的节点vis 数组标记 “已处理” 的节点避免重复松弛核心优化否则会超时节点编号题目中节点几乎都是 1-based从 1 开始输出循环要写i1到n。注意#includebits/stdc.h using namespace std; const int N 100010; // 节点数量上限根据题目调整 const int inf 0x3f3f3f3f; // 代表无穷大表示节点不可达不是负无穷 int n,m,s; // 全局变量n总节点数m边数s起点源节点 struct edge{ // 邻接表的边结构体 int v,w; // v当前边的终点w当前边的权重 }; int d[N],vis[N]; // d[N]存储起点s到每个节点的最短距离vis[N]标记节点是否已处理完成 vectoredge e[N]; // 邻接表核心e[a] 存储节点a的所有出边每个元素是edge结构体 // 优先队列大根堆存储负的最短距离, 节点编号利用负数实现小根堆效果优先取距离最小的节点 priority_queuepairint,int q; // Dijkstra核心函数求起点s到所有节点的最短距离 void dijkstra(int s){ memset(vis,0,sizeof vis); // 初始化所有节点都未处理0未处理1已处理 for(int i 0;in;i) d[i] inf; // 初始化起点到所有节点的距离设为无穷大不可达 d[s] 0; // 起点到自身的最短距离为0 q.push({0,s}); // 起点入队距离0, 节点s while(q.size()){ // 队列非空时循环还有节点待处理 auto t q.top();q.pop(); // 取出队头当前距离“最小”的节点并弹出队头 int u t.second; // 取出队头节点的编号pair的第二个元素是节点 if(vis[u]) continue; // 优化如果该节点已处理过直接跳过避免重复计算 vis[u] 1; // 标记该节点为“已处理”后续无需再处理 // 遍历节点u的所有出边执行“松弛操作” for(auto ed:e[u]){ int v ed.v,w ed.w; // vu的邻接节点wu→v的边权 // 松弛核心如果“起点→u→v”的距离 比 “起点→v”的已知距离更短就更新 if(d[v] d[u] w){ d[v] d[u] w; // 更新起点到v的最短距离 q.push({-d[v],v}); // 新距离取负入队大根堆变“小根堆”优先处理近的节点 } } } } int main(){ cinnms; // 输入节点数、边数、起点编号 while(m--){ // 输入m条边构建邻接表 int a,b,c; // a边的起点b边的终点c边的权重有向边 cinabc; e[a].push_back({b,c}); // 给节点a添加出边a→b权重c // 若为无向图需加e[b].push_back({a,c}); } dijkstra(s); // 执行Dijkstra算法计算最短距离 // 输出起点s到1~n号节点的最短距离节点编号默认从1开始 for(int i 1;in;i) coutd[i] ; return 0; }背诵模板includebits/stdc.h using namespace std; const int N 1e510, inf 0x3f3f3f3f; int n,m,s,d[N],vis[N]; struct edge{int v,w;}; vectoredge e[N]; priority_queuepairint,int q; void dijkstra(int s){ memset(vis,0,sizeof vis); fill(d,dN,inf); d[s]0; q.push({0,s}); while(q.size()){ auto tq.top(); q.pop(); int ut.second; if(vis[u]) continue; vis[u]1; for(auto ed:e[u]){ int ved.v,wed.w; if(d[v]d[u]w) d[v]d[u]w, q.push({-d[v],v}); } } } int main(){ cinnms; while(m--){ int a,b,c; cinabc; e[a].push_back({b,c}); } dijkstra(s); for(int i1;in;i) coutd[i] ; return 0; }P4779 【模板】单源最短路径标准版 - 洛谷模板题目记得把节点开大一点#includebits/stdc.h using namespace std; const int N 10000010; const int inf 0x3f3f3f3f; int d[N],vis[N]; struct edge{ int v,w; }; vectoredge e[N]; priority_queuepairint,int q; int n,m,s; void dijkstra(int s){ memset(vis,0,sizeof vis); fill(d,dN,inf); d[s] 0; q.push({0,s}); while(q.size()){ auto t q.top();q.pop(); int u t.second; if(vis[u]) continue; vis[u] 1; for(auto ed: e[u]){ int v ed.v,w ed.w; if(d[v]d[u]w){ d[v] d[u]w; q.push({-d[v],v}); } } } } int main(){ cinnms; while(m--){ int a,b,c; cinabc; e[a].push_back({b,c}); } dijkstra(s); for(int i 1;in;i){ coutd[i] ; } return 0; }第2题最短路径问题_牛客题霸_牛客网注意核心比较逻辑 距离小 则距离和权值一起更新 之后 距离一样 权重比较更新借用cost数组存放cost#includebits/stdc.h using namespace std; const int N 100010; const int inf 0x3f3f3f3f;//无穷大 struct edge{ int v,dis,w;//dis 距离 //w费用 }; vectoredge e[N];//邻接表头元素 int d[N],vis[N],cost[N]; priority_queuepairint,int q;//大根堆 int n,m; int a,b,dis,p; int s,t; //dijkstra算法 void dijkstra(int s){ memset(vis,0,sizeof vis);//数组初始化 fill(d,dN,inf);//数组填充为inf无穷大 fill(cost,costN,inf); d[s] 0,cost[s] 0;//起点初始化 q.push({0,s});//起点入队 while(q.size()){//边界条件判空 auto t q.top();//取队头元素 q.pop();//出队 auto u t.second;//取t的下一个节点编号 if(vis[u]) continue;//判断是否访问过 vis[u] 1; for(auto ed:e[u]){//遍历节点u的所有的边 int v ed.v, dis ed.dis, w ed.w;// 提取当前边的信息终点v、距离dis、费用w // 正确逻辑1.距离最短先更新 距离和费用 if(d[v]d[u]dis){ d[v] d[u]dis; cost[v] cost[u] w; q.push({-d[v],v}); }//距离一致 则比较费用 else if(d[v] d[u]discost[v]cost[u]w){ cost[v] cost[u]w; q.push({-d[v],v}); } } } } int main(){ // 循环读入多组测试用例直到输入n0且m0时结束 while(cinnm){ if(n0m0) break; // 读入m条边 无向图要两边一起 for(int i 0;im;i){ cinabdisp; // 无向边a→b 添加一条边终点b距离dis费用p e[a].push_back({b,dis,p}); // 无向边b→a 添加一条边终点a距离dis费用p e[b].push_back({a,dis,p}); } cinst; dijkstra(s); coutd[t] cost[t]endl; } return 0; }3.最短路径3488. 最短路径 - AcWing题库这个题目的测试点很奇怪 主要是学会这个dijkstra算法模板#includebits/stdc.h using namespace std; const int N 10010; const int inf 0x3f3f3f3f; const int P 100000; struct edge{ int v; long long w; }; vectoredge e[N]; long long dis[N]; int vis[N]; priority_queuepairlong long,int q; int n,m; void dijkstra(int s){ memset(vis,0,sizeof vis); fill(dis,disN,inf); dis[s] 0; q.push({0,s}); while(q.size()){ auto t q.top(); q.pop(); auto u t.second; if(vis[u]) continue; vis[u] 1; for(auto ed:e[u]){ int v ed.v, w ed.w; if(dis[v] dis[u]w) { dis[v] dis[u]w; q.push({-dis[v],v}); } } } } int main(){ cinnm;//无向图 for(int i 0;im;i){ int a,b; cinab; // 用 1LL i 计算 2^i纯整数运算无精度问题 long long w 1LL i; //存放路的权重 e[a].push_back({b,w}); e[b].push_back({a,w}); } dijkstra(0); for(int i 1;in;i){ if(dis[i] inf) cout-1endl; else printf(%d\n,dis[i]%P); } return 0; }