【1030】Travel Plan (30 分)

举报
野猪佩奇996 发表于 2022/01/23 00:56:26 2022/01/23
【摘要】 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm> #include<map>#inclu...

  
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<math.h>
  5. #include<string.h>
  6. #include<algorithm>
  7. #include<map>
  8. #include<vector>
  9. #include<queue>
  10. using namespace std;
  11. //dijkstra + DFS
  12. const int MAXV=510; //最大顶点数
  13. const int INF=0x3fffffff; //无穷大
  14. //n为顶点数,m为边数,st和ed分别为起点和终点
  15. //G为距离矩阵,cost为花费矩阵
  16. //d[]记录最短距离,minCost记录最短路径上的最小花费
  17. int n,m,st,ed,G[MAXV][MAXV],cost[MAXV][MAXV];
  18. int d[MAXV],minCost=INF;
  19. bool vis[MAXV]={false}; //vis[i]==true表示顶点i已访问,初值均为false
  20. vector<int> pre[MAXV];//前驱
  21. vector<int> tempPath,path; //临时路径,最优路径
  22. void Dijkstra(int s){ //s为起点
  23. fill(d,d+MAXV,INF); //fill函数将整个d数组赋为INF
  24. d[s]=0; //起点s到达自身的距离为0
  25. for(int i=0;i<n;i++){ //遍历n个顶点
  26. int u=-1,MIN=INF; //u使d[u]最小,MIN存放该最小的d[u]
  27. for(int j=0;j<n;j++){ //找到未访问的顶点中d[]最小的
  28. if(vis[j] == false && d[j] <MIN){
  29. u=j;
  30. MIN=d[j];
  31. }
  32. }
  33. //找不到小于INF的d[u],说明剩下的顶点和起点不连通
  34. if(u == -1) return ;
  35. vis[u]=true; //标记u为已访问
  36. for(int v=0;v<n;v++){
  37. //如果v未访问 && u能够到达v
  38. if(vis[v]==false && G[u][v] !=INF){
  39. if(d[u]+G[u][v] < d[v]){ //以u为中介点使d[v]更小
  40. d[v]=d[u]+G[u][v]; //优化d[v]
  41. pre[v].clear(); //清空pre[v]
  42. pre[v].push_back(u); //u为v的前驱
  43. }else if(d[u]+G[u][v] == d[v]) {//找到相同长度的路径
  44. pre[v].push_back(u); //u为v的前驱之一
  45. }
  46. }
  47. }
  48. }
  49. }
  50. void DFS(int v){ //v为当前结点
  51. if(v == st){ //递归边界,到达叶子结点(路径起点)
  52. tempPath.push_back(v);
  53. int tempCost=0; //记录当前路径的花费之和
  54. for(int i=tempPath.size()-1;i>0;i--){ //倒着访问
  55. //当前结点id、下个结点idNext
  56. int id=tempPath[i] , idNext=tempPath[i-1];
  57. tempCost += cost[id][idNext]; //增加边id->idNext的边权
  58. }
  59. if(tempCost < minCost){ //如果当前路径的边权之和更小
  60. minCost=tempCost; //更新minCost
  61. path=tempPath; //更新path
  62. }
  63. tempPath.pop_back();//将刚才加入的结点删除
  64. return;
  65. }
  66. tempPath.push_back(v); //将当前访问结点加入临时路径tempPath最后面
  67. for(int i=0;i<pre[v].size();i++){
  68. DFS(pre[v][i]);
  69. }
  70. tempPath.pop_back();//遍历完所有前驱结点,将当前结点v删除
  71. }
  72. int main(){
  73. scanf("%d%d%d%d",&n,&m,&st,&ed);
  74. int u,v;
  75. fill(G[0],G[0]+MAXV*MAXV,INF);//初始化图G
  76. fill(cost[0],cost[0]+MAXV*MAXV,INF);
  77. for(int i=0; i<m; i++){
  78. scanf("%d%d",&u,&v);
  79. scanf("%d%d",&G[u][v], &cost[u][v]);
  80. G[v][u]=G[u][v]; //因为是无向图
  81. cost[v][u]=cost[u][v];
  82. }
  83. Dijkstra(st);
  84. DFS(ed); //获得最优路径
  85. for(int i=path.size()-1; i>=0; i--){
  86. printf("%d ",path[i]); //倒着输出路径上的结点
  87. }
  88. printf("%d %d\n",d[ed],minCost); //最短距离,最短路径上的最小花费
  89. system("pause");
  90. return 0;
  91. }

 

文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。

原文链接:andyguo.blog.csdn.net/article/details/99687540

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。