Dijkstra 模板 最短路
模板 短路 Dijkstra
2023-09-14 09:07:58 时间
转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents
------------------------------------------------------------------------------------------------------------------------------------------------------
欢迎光临天资小屋:http://user.qzone.qq.com/593830943/main
------------------------------------------------------------------------------------------------------------------------------------------------------
模板奉上:(HDU2544)
#include <cstdio> #include <iostream> #include <algorithm> #define MAXN 117 #define INF 0x3fffffff using namespace std; int mat[MAXN][MAXN]; int n,m;//n为结点数,m为道路数 int dijkstra (int s,int f) { //s为起点, f:为终点 int dis[MAXN];//记录到随意点的最短距离 int mark[MAXN];//记录被选中的结点 int i, j, k; for(i = 1; i <= n; i++) { mark[i] = 0;//初始化全部结点。每一个结点都没有被选中 dis[i] = INF; //dis[i] = mat[s][i]; } mark[s] = 1;//start结点被选中 dis[s] = 0;//将start结点的的距离设置为0 int min;//设置最短的距离。 for(i = 1; i <= n; i++) { k = 1;//赋初值非常重要 min = INF; for(j = 1; j <= n;j++) { if(!mark[j] && dis[j] < min)//未被选中的结点中,距离最短的被选中 { min = dis[j] ; k = j; } } mark[k] = 1;//标记为被选中 for(j = 1; j <= n; j++) { if(!mark[j] && dis[j]>dis[k] + mat[k][j])//改动剩余结点的最短距离 { dis[j] = dis[k] + mat[k][j]; } } } return dis[f]; } void init() { for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { if(i == j) mat[i][j] = 0; else mat[i][j] = INF; } } } int main() { int i,j; int a,b,dis; while(scanf("%d %d",&n,&m)) { if(n == 0 || m == 0) break; init(); for(i = 1; i <= m; i++) { scanf("%d %d %d",&a,&b,&dis); if(dis < mat[a][b] || dis < mat[b][a]) mat[a][b] = mat[b][a] = dis; } int ans = dijkstra(1,n); printf("%d\n",ans); } return 0; }
相关文章
- es6模板字符串_es6模板差值
- 标准地图的矢量模板,ArcGIS可打开
- Typecho教程 - 获取模板自定义字段值
- autpoi 1.4.3版本发布—Excel傻瓜式API,快速实现Excel导入导出、Word模板导出
- VUE中的模板语法以及过滤器和双向数据绑定
- 快速搭建基于Vue3+Vite2+Arco+Typescript+Pinia后台管理系统模板,文末有福利
- SpringMVC自定义异常处理器简单模板
- 使用Spring提供的RestTemplate模板类出现,中文乱码问题,解决方法
- JavaScript刷LeetCode模板技巧篇(一)2
- 「.vue文件的编译」5. 模板编译之基于AST的代码生成
- 999+套各色风格PPT模板,简约纯色通用PPT模板:好看的模板随意选择
- WordPress 主题教程 #4a:Header 模板
- 个人网站前端模板收集(网站模板)
- vue attribute中使用字符串模板 template string详解编程语言
- 利用Oracle分区模板优化数据管理(oracle分区模板)
- PyGame Zero: 无需模板的游戏开发
- 掌握Oracle中的日期模板(oracle中日期模板)
- ASP高级模板引擎实现类
- C++模板类的用法实例
- Thinkphp模板没有解析直接原样输出的解决方法
- mysql配置模板(my-*.cnf)参数详细说明