首页 > 代码库 > HDU 2544 最短路
HDU 2544 最短路
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2544
解析:
首先数据量为V<=100
那么这里使用任何基础的最短路的算法都不会超时!
常见数据:
5 6 1 2 10 1 3 4 2 4 2 3 4 3 2 5 5 4 5 100 // 答案:14 2 4 1 2 10 1 3 4 2 4 2 3 4 3 // 答案:9
Bellman-Ford算法:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> using namespace std; #define MAX_E 10010 #define MAX_V 105 #define INF 1e8 struct edge{int from, to, cost; }; edge es[2*MAX_E]; int d[MAX_V]; int V, E; void shortest_path(int s){ for(int i=1; i<=V; ++i) d[i] = INF; d[s] = 0; while(true){ bool update = false; for(int i=0; i<2*E; ++i){ edge e = es[i]; if(d[e.from] != INF&&d[e.to]>d[e.from]+e.cost){ d[e.to] = d[e.from] + e.cost; update = true; } } if(!update) break; } } int main(){ while(~scanf("%d%d", &V, &E), V||E){ int i; int a,b,c; for(i=0; i<E; ++i){ scanf("%d%d%d", &a, &b, &c); es[i].from = a; es[i].to = b; es[i].cost = c; es[i+E].from = b; es[i+E].to = a; es[i+E].cost = c; } shortest_path(1); printf("%d\n", d[V]); } }
Dijkstra算法:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #include <cstring> #include <string> using namespace std; #define MAX_V 105 #define MAX_X 105 #define INF 1e8 int cost[MAX_V][MAX_V]; int d[MAX_X]; bool used[MAX_X]; int n,m; void dijkstra(int s){ for(int i=1; i<=n; ++i){ d[i] = INF; used[i] = false; } d[s] = 0; while(true){ int v = -1; for(int u=1; u<=n; ++u){ if(!used[u]&&(v==-1||d[u]<d[v])) v = u; } if(v == -1) break; used[v] = true; for(int u=1; u<=n; ++u){ d[u] = min(d[u], d[v]+cost[v][u]); } } } int main(){ while(~scanf("%d%d", &n, &m), m||n){ int i; int a,b,c; for(i=1; i<=n; ++i) for(int j=1; j<=n; ++j) cost[i][j] = INF; for(i=0; i<m; ++i){ scanf("%d%d%d", &a, &b, &c); cost[a][b] = c; cost[b][a] = c; } dijkstra(1); printf("%d\n", d[n]); } }
Floyd算法:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> using namespace std; #define MAX_V 105 #define MAX_X 105 #define INF 1e8 int d[MAX_V][MAX_V]; bool used[MAX_X]; int n,m; void floyd(){ for(int k=1; k<=n; ++k){ for(int i=1; i<=n; ++i){ for(int j=1; j<=n; ++j){ d[i][j] = min(d[i][j], d[i][k]+d[k][j]); } } } } int main(){ while(~scanf("%d%d", &n, &m), m||n){ int i; int a,b,c; for(i=1; i<=n; ++i) for(int j=1; j<=n; ++j) d[i][j] = INF; for(i=1; i<=n; ++i) d[i][i] = 0; for(i=0; i<m; ++i){ scanf("%d%d%d", &a, &b, &c); d[a][b] = c; d[b][a] = c; } floyd(); printf("%d\n", d[1][n]); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。