dijkstra第二标尺模板
2022/2/9 6:13:38
本文主要是介绍dijkstra第二标尺模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
dijkstra版
for(int v = 0; v < n; v++) { if(visit[v] == false && e[u][v] != inf) { if(dis[u] + e[u][v] < dis[v]) { dis[v] = dis[u] + e[u][v]; w[v] = w[u] + weight[v]; }else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) { w[v] = w[u] + weight[v]; } } }
dijkstra+dfs版
void dfs(int v) { if(v == s) { temppath.push_back(v); int tempcost = 0; for(int i = temppath.size() - 1; i > 0; i--) { int id = temppath[i], nextid = temppath[i-1]; tempcost += cost[id][nextid]; } if(tempcost < mincost) { mincost = tempcost; path = temppath; } temppath.pop_back(); return ; } temppath.push_back(v); for(int i = 0; i < pre[v].size(); i++) dfs(pre[v][i]); temppath.pop_back(); }
解释:
对于递归边界而言,如果当前访问的是叶子节点(路径的开始节点),那么说明到达了递归边界,把v压入tempath,tempath里面保存了一条完整路径。如果计算得到的当前的value大于最大值,就path=tempath。然后把tempath的最后一个结点弹出,return
对于递归式而言,每一次都是把当前访问的结点压入,然后找它的pre[v][i],进行递归,递归完毕弹出最后一个结点
(参考自柳神笔记)
这篇关于dijkstra第二标尺模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现