HDU 2544 最短路(各种最短路算法的实现)

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2544

 

题目：

 

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
 

 

 

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

 

 

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

 

 

Sample Input


 

2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0

 

 

Sample Output


 

3 2

 

 

Source

UESTC 6th Programming Contest Online

 

 

 

 

基础最短路，不解释，其实是专门用来验证各种最短路模板的。

 

 

1.    Dijkstra  普通版

 


 

  1. #include<cstdio>

  2. #include<cstring>

  3. const int N=105, INF=9999999;

  4. int d[N], w[N][N],vis[N],n,m;

  5.  

  6. void Dijkstra(int src){

  7. for(int i=1; i<=n; ++i)

  8. d[i] = INF;

  9. d[src] = 0;

  10. memset(vis, 0, sizeof(vis));

  11. for(int i=1; i<=n; ++i){

  12. int u=-1;

  13. for(int j=1; j<=n; ++j)if(!vis[j]){

  14. if(u==-1 || d[j]<d[u]) u=j;

  15. }

  16. vis[u] = 1;

  17. for(int j=1; j<=n; ++j)if(!vis[j]){

  18. int tmp = d[u] + w[u][j];

  19. if(tmp<d[j]) d[j] = tmp;

  20. }

  21. }

  22. }

  23. int main(){

  24. int a,b,c;

  25. while(~scanf("%d%d",&n,&m)&&n+m){

  26. for(int i=1; i<=n; ++i){

  27. w[i][i] = INF;

  28. for(int j=i+1; j<=n; ++j)

  29. w[i][j] = w[j][i] = INF;

  30. }

  31. for(int i=0; i<m; ++i){

  32. scanf("%d%d%d",&a,&b,&c);

  33. w[a][b] = w[b][a] = c;

  34. }

  35. Dijkstra(1);

  36. printf("%d\n", d[n]);

  37. }

  38. return 0;

  39. }

 

 

2. Dijkstra+邻接表(用数组实现)+优先队列优化

 


 

  1. #include<cstdio>

  2. #include<cstring>

  3. #include<utility>

  4. #include<queue>

  5. using namespace std;

  6.  

  7. const int N=20005;

  8. const int INF=9999999;

  9.  

  10. typedef pair<int,int>pii;

  11. priority_queue<pii, vector<pii>, greater<pii> >q;

  12.  

  13. int d[N], first[N], u[N], v[N], w[N], next[N],n,m;

  14. bool vis[N];

  15.  
  16.  

  17. // 无向图的输入，注意每输入的一条边要看作是两条边

  18. void read_graph(){

  19. memset(first, -1, sizeof(first)); //初始化表头

  20. for(int e=1; e<=m; ++e){

  21. scanf("%d%d%d",&u[e], &v[e], &w[e]);

  22. u[e+m] = v[e]; v[e+m] = u[e]; w[e+m] = w[e]; // 增加一条它的反向边

  23.  

  24. next[e] = first[u[e]]; // 插入链表

  25. first[u[e]] = e;

  26.  

  27. next[e+m] =first[u[e+m]]; // 反向边插入链表

  28. first[u[e+m]] = e+m;

  29. }

  30. }

  31.  

  32. void Dijkstra(int src){

  33. memset(vis, 0, sizeof(vis));

  34. for(int i=1; i<=n; ++i) d[i] = INF;

  35. d[src] = 0;

  36. q.push(make_pair(d[src], src));

  37. while(!q.empty()){

  38. pii u = q.top(); q.pop();

  39. int x = u.second;

  40. if(vis[x]) continue;

  41. vis[x] = true;

  42. for(int e = first[x]; e!=-1; e=next[e]) if(d[v[e]] > d[x]+w[e]){

  43. d[v[e]] = d[x] + w[e];

  44. q.push(make_pair(d[v[e]], v[e]));

  45. }

  46. }

  47. }

  48.  

  49. int main(){

  50. int a,b,c;

  51. while(~scanf("%d%d",&n,&m)&&n+m){

  52. read_graph();

  53. Dijkstra(1);

  54. printf("%d\n", d[n]);

  55. }

  56. return 0;

  57. }

 

 

3. Dijkstra+邻接表(用vecor实现)+优先队列优化

 

 


 

  1. #include<cstdio>

  2. #include<cstring>

  3. #include<utility>

  4. #include<queue>

  5. #include<vector>

  6. using namespace std;

  7.  

  8. const int N=105;

  9. const int INF=9999999;

  10.  

  11. typedef pair<int,int>pii;

  12. vector<pii>G[N];

  13. priority_queue<pii, vector<pii>, greater<pii> >q;

  14.  

  15. int d[N], first[N], u[N], v[N], w[N], next[N],n,m;

  16. bool vis[N];

  17.  
  18.  

  19. // 无向图的输入，注意没输入的一条边要看作是两条边

  20. void read_graph(){

  21. for(int i=1; i<=n; ++i)

  22. G[i].clear();

  23. int a,b,c;

  24. for(int i=1; i<=m; ++i){

  25. scanf("%d%d%d",&a,&b,&c);

  26. G[a].push_back(make_pair(b,c));

  27. G[b].push_back(make_pair(a,c));

  28. }

  29. }

  30.  

  31. void Dijkstra(int src){

  32. memset(vis, 0, sizeof(vis));

  33. for(int i=1; i<=n; ++i) d[i] = INF;

  34. d[src] = 0;

  35. q.push(make_pair(d[src], src));

  36. while(!q.empty()){

  37. pii t = q.top(); q.pop();

  38. int u = t.second;

  39. if(vis[u]) continue;

  40. vis[u] = true;

  41. for(int v=0; v<G[u].size(); ++v)if(d[G[u][v].first] > d[u]+G[u][v].second){

  42. d[G[u][v].first] = d[u]+G[u][v].second;

  43. q.push(make_pair(d[G[u][v].first], G[u][v].first));

  44. }

  45. }

  46. }

  47.  

  48. int main(){

  49. int a,b,c;

  50. while(~scanf("%d%d",&n,&m)&&n+m){

  51. read_graph();

  52. Dijkstra(1);

  53. printf("%d\n", d[n]);

  54. }

  55. return 0;

  56. }

 

 

 


 

二，Bellman-Ford算法

 


 

  1. #include<cstdio>

  2. #include<cstring>

  3. #include<utility>

  4. #include<queue>

  5. using namespace std;

  6.  

  7. const int N=20005;

  8. const int INF=9999999;

  9.  

  10. int n, m, u[N],v[N],w[N], d[N];

  11.  
  12.  

  13. // 无向图的输入，注意每输入的一条边要看作是两条边

  14. inline void read_graph(){

  15. for(int e=1; e<=m; ++e){

  16. scanf("%d%d%d",&u[e],&v[e],&w[e]);

  17. }

  18. }

  19.  

  20. inline void Bellman_Ford(int src){

  21. for(int i=1; i<=n; ++i) d[i] = INF;

  22. d[src] = 0;

  23. for(int k=0; k<n-1; ++k){

  24. for(int i=1; i<=m; ++i){

  25. int x=u[i], y=v[i];

  26. if(d[x] < INF){

  27. if(d[y]>d[x]+w[i])

  28. d[y] = d[x]+w[i];

  29. }

  30. if(d[y] < INF){

  31. if(d[x]>d[y]+w[i])

  32. d[x] = d[y]+w[i];

  33. }

  34. }

  35. }

  36. }

  37.  

  38. int main(){

  39. int a,b,c;

  40. while(~scanf("%d%d",&n,&m)&&n+m){

  41. read_graph();

  42. Bellman_Ford(1);

  43. printf("%d\n", d[n]);

  44. }

  45. return 0;

  46. }

 

 

三，SPFA

邻接表实现

 


 

  1. #include<cstdio>

  2. #include<cstring>

  3. #include<utility>

  4. #include<queue>

  5. using namespace std;

  6.  

  7. const int N=20005;

  8. const int INF=2147483646>>1;

  9.  

  10. int n, m, first[N],next[N],u[N],v[N],w[N], d[N];

  11. bool vis[N];

  12.  

  13. queue<int>q;

  14.  

  15. inline void read_graph(){

  16. memset(first, -1, sizeof(first));

  17. for(int e=1; e<=m; ++e){

  18. scanf("%d%d%d",&u[e],&v[e],&w[e]);

  19. u[e+m]=v[e], v[e+m]=u[e], w[e+m]=w[e];

  20. next[e] = first[u[e]];

  21. first[u[e]] = e;

  22. next[e+m] = first[u[e+m]];

  23. first[u[e+m]] = e+m;

  24. }

  25. }

  26.  

  27. void SPFA(int src){

  28. memset(vis, 0, sizeof(vis));

  29. for(int i=1; i<=n; ++i) d[i] = INF;

  30. d[src] = 0;

  31. vis[src] = true;

  32.  

  33. q.push(src);

  34. while(!q.empty()){

  35. int x = q.front(); q.pop();

  36. vis[x] = false;

  37. for(int e=first[x]; e!=-1; e=next[e]){

  38. if(d[x]+w[e] < d[v[e]]){

  39. d[v[e]] = d[x]+w[e];

  40. if(!vis[v[e]]){

  41. vis[v[e]] = true;

  42. q.push(v[e]);

  43. }

  44. }

  45. }

  46. }

  47. }

  48.  

  49. int main(){

  50. int a,b,c;

  51. while(~scanf("%d%d",&n,&m)&&n+m){

  52. read_graph();

  53. SPFA(1);

  54. printf("%d\n", d[n]);

  55. }

  56. return 0;

  57. }

 

 

 

四， Floyd算法

 


 

  1. #include<cstdio>

  2. #include<cstring>

  3. #include<utility>

  4. #include<queue>

  5. using namespace std;

  6.  

  7. const int N=105;

  8. const int INF=2147483646;

  9.  

  10. int n, m, d[N][N];

  11.  
  12.  

  13. inline void read_graph(){

  14. for(int i=1; i<=n; ++i){

  15. d[i][i] = INF;

  16. for(int j=i+1; j<=n; ++j)

  17. d[i][j]=d[j][i]=INF;

  18. }

  19. int a,b,c;

  20. for(int e=1; e<=m; ++e){

  21. scanf("%d%d%d",&a,&b,&c);

  22. d[a][b]=d[b][a]=c;

  23. }

  24. }

  25.  

  26. inline void Floyd(int src){

  27. for(int k=1; k<=n; ++k){

  28. for(int i=1; i<=n; ++i){

  29. for(int j=1; j<=n; ++j)

  30. if(d[i][k]<INF && d[k][j]<INF){ //防止溢出

  31. d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

  32. }

  33. }

  34. }

  35. }

  36.  

  37. int main(){

  38. int a,b,c;

  39. while(~scanf("%d%d",&n,&m)&&n+m){

  40. read_graph();

  41. Floyd(1);

  42. printf("%d\n", d[1][n]);

  43. }

  44. return 0;

  45. }

 

 

 


 

——  生命的意义，在于赋予它意义。

          

     原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)

全部评论

相关推荐

11-06 11:10
远景_数据算法工程师(准入职员工)
远景能源内推，远景能源内推码
1⃣个人BG基本：学历背景：上海某211本、985硕，经管类专业rank4，GPA4.12投递岗位：交付体系（和供应链管理强相关）实习经历：有过2段强相关实习经历【一段世界500强（Gartner前10）、一段民企】求职目标：朝阳行业的供应链管理方向岗位👌🏻最终去向：斩获6个offer，最终选择远景能源！2⃣薪酬福利base：硕士&nbsp;16&nbsp;k-17k&nbsp;×&nbsp;15～18&nbsp;薪（看绩效档位）其他福利：六险一金、10&nbsp;天年假【这点我觉得很牛】横向对比：我同届拿到某科技13k&nbsp;×&nbsp;14；外企15&nbsp;k&nbsp;×&nbsp;163⃣今年秋招扩招还是缩？内部口径：CEO&nbsp;张雷对校招生“种子”的培养支持力度大，倡导&nbsp;“合规从娃...
点赞 评论 收藏
分享
11-07 09:54
江苏网商精益管理软件有限公司_工程部_后端开发(实习员工)
武汉-作业帮-三面-HR面
1.&nbsp;自我介绍2.&nbsp;家是在哪里的？3.&nbsp;实习base地在哪里？4.&nbsp;找工作，会考虑哪些点？5.&nbsp;为什么会考虑武汉？6.&nbsp;为什么实习的时候不去武汉呢？7.&nbsp;发展前景，团队氛围，主要是看哪些呢？8.&nbsp;京东实习过程的感受与收获？9.&nbsp;实习项目和学校经验，对比？10.&nbsp;实习期间最大的挑战是什么？11.&nbsp;实习的时候组有多少人？是否涉及跨部门合作呢？12.&nbsp;实习是否分配mentor呢？mentor给了什么样的帮助呢？13.&nbsp;工作中，遇到问题，除了问mentor，还有什么措施呢？14.&nbsp;为什么不考虑转正呢？15.&nbsp;工作节奏怎么样？怎么样工作节奏是合适的呢？16.&nbsp;几月份开始看秋招的呢？手里是否在流程中？17...
点赞 评论 收藏
分享
09-18 20:41
阿里巴巴_后端
秋招难度就这？
又拿到两个offer&nbsp;哈哈哈哈哈好开心
要个offer怎么这...：哈哈哈哈哈哈，我也拿了0x10000000个offer，秋招温啦啦啦，好开心
我的秋招日记
点赞 评论 收藏
分享
11-07 10:58
OPPO_软件开发部_IT开发工程师(准入职员工)
海康威视内推，海康威视内推码
岗位：武汉&nbsp;嵌入式开发timeline：8.30&nbsp;测评，10.9&nbsp;一面，10.11&nbsp;二面一面技术：自我介绍讲下实习经历平常怎么debug项目中有没有遇到什么问题，怎么解决的介绍一下学校经历了解数据结构吗？基本的数据结构？查找搜索效率？有什么方法可以提高效率？具体围绕数据结构问了很多RTOS，多任务操作反问：做存储固件的，具体的进来再分二面HR：北京线下，地点在北京研发中心，具体内容就是唠家常，一些HR面的基本问题销售工程师工作体验，总结累但成长很多。1.大家最先关注的就是HIK的工作压力，只能说体面厂没有辜负盛名！名不虚传！我来这边是销售岗，基本上每天都要差不多11点下班。因为销售不仅需要对接...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 联影医疗求职进展汇总 #
14004次浏览 69人参与
# 本机械人被这些公司泡过池子 #
38279次浏览 185人参与
# 联影求职进展汇总 #
58974次浏览 368人参与
# CVTE求职进展汇总 #
24383次浏览 323人参与
# 中核求职进展汇总 #
29667次浏览 193人参与
# 海康威视工作体验 #
46912次浏览 158人参与
# 京东开奖 #
481520次浏览 2703人参与
# 外包能不能当跳板？ #
48810次浏览 245人参与
# 哪些公司校招卡第一学历 #
221623次浏览 779人参与
# 机械人与华为的爱恨情仇 #
138648次浏览 1013人参与
# 嵌入式岗知多少 #
59916次浏览 548人参与
# 2022毕业即失业取暖地 #
117750次浏览 707人参与
# 毕业论文进行时 #
8406次浏览 86人参与
# 找实习你看重大厂光环还是业务方向 #
42689次浏览 164人参与
# 同bg的你秋招战况如何？ #
176989次浏览 1034人参与
# 面对逼签的应对技巧 #
9524次浏览 42人参与
# 秋招什么时候开投比较合适？ #
112626次浏览 814人参与
# 说说你知道的学历厂 #
359203次浏览 1286人参与
# 我来点评面试官 #
18501次浏览 121人参与
# 校招薪资来揭秘 #
2732次浏览 18人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务