【朴素Dijkstra】AcWing849.Dijkstra求最短路 I
2022/5/24 23:52:42
本文主要是介绍【朴素Dijkstra】AcWing849.Dijkstra求最短路 I,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AcWing849.Dijkstra求最短路 I
题解
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 510, M = 1e5 + 10; int d[N], n, m; bool flag[N]; int g[N][N]; //朴素只能用邻接矩阵不然会变成O(nm) void Dijkstra() { memset(d, 0x3f, sizeof d); d[1] = 0; for(int i = 0; i < n; ++i) { int mi = 0x3f3f3f, k; for(int j = 1; j <= n; ++j) if(!flag[j] && d[j] < mi) mi = d[j], k = j; flag[k] = true; for(int j = 1; j <= n; ++j) if(!flag[j] && mi + g[k][j] < d[j]) d[j] = mi + g[k][j]; } } int main() { memset(g, 0x3f, sizeof g); int x, y, z; scanf("%d%d",&n,&m); for(int i = 0 ;i < m; ++i) { scanf("%d%d%d",&x,&y,&z); g[x][y] = min(g[x][y], z); } Dijkstra(); if(flag[n]) cout << d[n] << endl; else cout << -1 << endl; return 0; }
这篇关于【朴素Dijkstra】AcWing849.Dijkstra求最短路 I的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!