最短路 HDU - 2544 (dijkstra算法或Floyd算法)
算法 HDU 短路 Dijkstra Floyd
2023-09-11 14:19:01 时间
![](https://img2018.cnblogs.com/blog/1435569/201907/1435569-20190725161819272-367380260.png)
Dijkstra解法:
1 #include <stdio.h> 2 #include <iostream> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 #include <sstream> 7 8 #define INF 1000000000 9 10 using namespace std; 11 int N, M; 12 int dist[101],g[101][101]; 13 int vis[101]; 14 15 16 void dijkstra(int start) 17 { 18 for(int i = 1; i <= N; ++i) 19 { 20 dist[i] = g[start][i]; 21 vis[i] = 0; 22 } 23 vis[start] = 1; 24 25 while(1) 26 { 27 int mark = -1, minDist = INF; 28 for(int i = 1; i <= N; ++i) 29 { 30 if(!vis[i] && dist[i] < minDist) 31 { 32 minDist = dist[i]; 33 mark = i; 34 } 35 } 36 37 if(mark == -1) // 找不到未收录的节点,则说明算法结束,退出 38 break; 39 40 vis[mark] = 1; 41 42 for(int i = 1; i <= N; ++i) 43 { 44 if(!vis[i]) 45 dist[i] = min(dist[i], dist[mark] + g[mark][i]); 46 } 47 } 48 } 49 50 int main() 51 { 52 while(cin >> N >> M) 53 { 54 if(N == 0 && M == 0) 55 break; 56 57 for(int i = 1; i <= N; ++i) 58 for(int j = 1; j <= N; ++j) 59 { 60 if(i == j) 61 g[i][j] = 0; 62 else 63 g[i][j] = INF; 64 } 65 66 for(int i = 1; i <= M; ++i) 67 { 68 int a,b,c; 69 cin >> a >> b >> c; 70 g[a][b] = g[b][a] = c; 71 } 72 73 dijkstra(1); 74 cout << dist[N] << endl; 75 76 } 77 78 return 0; 79 }
Floyd解法:
1 #include <stdio.h> 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 #include <algorithm> 6 #include <sstream> 7 8 using namespace std; 9 10 int dis[101][101]; 11 12 int main() 13 { 14 int N, M; 15 while(cin >> N >> M) 16 { 17 if(N == 0 && M == 0) 18 break; 19 20 for(int i = 1; i <= N; ++i) 21 { 22 for(int j = 1; j <= N; ++j) 23 { 24 if(i == j) 25 dis[i][j] = 0; 26 else 27 dis[i][j] = 1100000; 28 } 29 } 30 31 int a, b, c; 32 for(int i = 1; i <= M; ++i) 33 { 34 cin >> a >> b >> c; 35 if(dis[a][b] > c) 36 dis[a][b] = dis[b][a] = c; 37 38 } 39 40 for(int k = 1; k <= N; ++k) 41 for(int i = 1; i <= N; ++i) 42 for(int j = 1; j <= N; ++j) 43 { 44 if(dis[i][j] > dis[i][k] + dis[k][j]) 45 dis[i][j] = dis[i][k] + dis[k][j]; 46 } 47 48 cout << dis[1][N] << endl; 49 } 50 51 52 53 54 return 0; 55 }
相关文章
- HDU 4712 Hamming Distance(随机算法)
- 排序算法
- 用Java来写常见的排序算法
- 【学习总结】小象学院-算法面试课程
- 【hdu 2108】Shape of HDU
- DL之AlexNet:AlexNet算法的架构详解、损失函数、网络训练和学习之详细攻略
- DL之CNN:计算机视觉之卷积神经网络经典算法简介、重要进展、改进技巧之详细攻略(建议收藏)
- 基于多目标粒子群优化算法的计及光伏波动性的主动配电网有功无功协调优化(Matlab代码实现)
- 基于混合VNS(变邻域搜索算法)的PSO(粒子群优化算法)的任务分配问题(Matlab代码实现)
- 516. 最长回文子序列-动态规划算法
- HDU 5289 Assignment (ST算法区间最值+二分)
- JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序
- 双指针算法模板和一些题目
- 排序算法之插入排序