[关闭]
@Chilling 2017-04-19T20:09:08.000000Z 字数 6624 阅读 1290

HDU-2544: 最短路(dij+优先队列+邻接表 | 邻接矩阵)

最短路


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

邻接矩阵

将两点之间的信息保存在邻接矩阵中,使用dijkstra算法寻找最短路。dis数组存入的是从起点到某点的最短距离,最开始初始化要最大,因此memset(dis,127,sizeof(dis));在dij函数中每找到短的一条路径就根据这一路径更新其他路径。

  1. while(m--)
  2. {
  3. scanf("%d%d%d",&a,&b,&c);
  4. if(c<ma[a][b])
  5. {
  6. ma[a][b]=c;
  7. ma[b][a]=c; //双向
  8. }
  9. }
  1. void dij()
  2. {
  3. int i,j,x,pos;
  4. for(i=1;i<=n;i++)
  5. dis[i]=ma[1][i]; //从1到i点的距离
  6. vis[1]=1; //标记起点
  7. for(i=1;i<n;i++) //n个点,也就是该题中的路口
  8. {
  9. x=INF;
  10. for(j=1;j<=n;j++)
  11. {
  12. if(vis[j]==0&&dis[j]<x) //没有经过某位置
  13. {
  14. x=dis[j]; //从所有没有标记的点中,选择一个dis最小的
  15. pos=j;
  16. }
  17. }
  18. vis[pos]=1; //标记这个最小的点
  19. for(j=1;j<=n;j++) //并且用这个最小的点更新其他路径
  20. if(vis[j]==0&&dis[j]>dis[pos]+ma[pos][j]) //如果经过pos点再到j的距离比原来的更短,更新
  21. dis[j]=dis[pos]+ma[pos][j];
  22. }
  23. }
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define INF 1e9
  4. int ma[111][111],m,n,dis[111],vis[111];
  5. void dij()
  6. {
  7. int i,j,x,pos;
  8. for(i=1;i<=n;i++)
  9. dis[i]=ma[1][i]; //从1到i点的距离
  10. vis[1]=1;
  11. for(i=1;i<n;i++)
  12. {
  13. x=INF;
  14. for(j=1;j<=n;j++)
  15. {
  16. if(vis[j]==0&&dis[j]<x)
  17. {
  18. x=dis[j];
  19. pos=j;
  20. }
  21. }
  22. vis[pos]=1;
  23. for(j=1;j<=n;j++)
  24. if(vis[j]==0&&dis[j]>dis[pos]+ma[pos][j]) //如果经过pos点再到j的距离比原来的更短,更新
  25. dis[j]=dis[pos]+ma[pos][j];
  26. }
  27. }
  28. int main()
  29. {
  30. int a,b,c;
  31. while(scanf("%d%d",&n,&m),n+m)
  32. {
  33. memset(ma,127,sizeof(ma));
  34. memset(vis,0,sizeof(vis));
  35. while(m--)
  36. {
  37. scanf("%d%d%d",&a,&b,&c);
  38. if(c<ma[a][b])
  39. {
  40. ma[a][b]=c;
  41. ma[b][a]=c; //双向
  42. }
  43. }
  44. dij();
  45. printf("%d\n",dis[n]);
  46. }
  47. return 0;
  48. }

邻接表

邻接表可以用于无向图,也可以用于有向图,用数组实现链表,比vector的时间复杂度更低一点。

  1. void add(int st,int en,int val)
  2. {
  3. a[num].en=en;
  4. a[num].val=val;
  5. a[num].next=pos[st];
  6. pos[st]=num;
  7. num++;
  8. }
  1. void dij()
  2. {
  3. int i,j,x,id;
  4. dis[1]=0; //起点
  5. for(i=1;i<=n;i++)
  6. {
  7. x=INF;
  8. for(j=1;j<=n;j++)
  9. {
  10. if(vis[j]==0&&dis[j]<x) //没有经过并且距离更短,就使用这个点
  11. {
  12. x=dis[j]; //从所有没有标记的点中,选择一个dis最小的
  13. id=j;
  14. }
  15. }
  16. vis[id]=1; //使用后标记
  17. for(j=pos[id];j!=-1;j=a[j].next) //与这个点相连的其他点
  18. {
  19. if(dis[a[j].en]>dis[id]+a[j].val) //如果原来到这点的距离比现在的更长,用现在的距离更新
  20. dis[a[j].en]=dis[id]+a[j].val;
  21. }
  22. }
  23. }
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define INF 1e9
  4. struct node
  5. {
  6. int en,val,next;
  7. }a[100005];
  8. int vis[111],pos[111],dis[111],num,n,m;
  9. void add(int st,int en,int val)
  10. {
  11. a[num].en=en;
  12. a[num].val=val;
  13. a[num].next=pos[st]; //好像是加到前面的意思……再理解= =不行就记住
  14. pos[st]=num;
  15. num++;
  16. }
  17. void dij()
  18. {
  19. int i,j,x,id;
  20. dis[1]=0; //起点
  21. for(i=1;i<=n;i++)
  22. {
  23. x=INF;
  24. for(j=1;j<=n;j++)
  25. {
  26. if(vis[j]==0&&dis[j]<x) //没有经过并且距离更短,就使用这个点
  27. {
  28. x=dis[j];
  29. id=j;
  30. }
  31. }
  32. vis[id]=1; //使用后标记
  33. for(j=pos[id];j!=-1;j=a[j].next) //这里也不是很清楚
  34. {
  35. if(dis[a[j].en]>dis[id]+a[j].val) //如果原来到这点的距离比现在的更长,用现在的距离更新
  36. dis[a[j].en]=dis[id]+a[j].val;
  37. }
  38. }
  39. }
  40. int main()
  41. {
  42. int a,b,c;
  43. while(scanf("%d%d",&n,&m),n+m)
  44. {
  45. memset(vis,0,sizeof(vis));
  46. memset(pos,-1,sizeof(pos));
  47. memset(dis,127,sizeof(dis)); //距离初始化最大值
  48. num=0;
  49. while(m--)
  50. {
  51. scanf("%d%d%d",&a,&b,&c);
  52. add(a,b,c);
  53. add(b,a,c); //无向图,添加两个方向
  54. }
  55. dij();
  56. printf("%d\n",dis[n]); //到n的最短时间
  57. }
  58. return 0;
  59. }

邻接表+优先队列优化

如果不用优先队列优化,每次找到最短距离需要二重循环,复杂度为,使用优先队列,复杂度为
其实这个并不是很懂……都是照着模板打的

  1. struct node2
  2. {
  3. int id,val; //id是尾位置吧大概……
  4. node2(int id1=0,int val1=0) //构造函数
  5. {
  6. id=id1;val=val1;
  7. }
  8. friend bool operator <(node2 x,node2 y) //重载<符号
  9. {
  10. return x.val>y.val;
  11. }
  12. };
  1. void dij()
  2. {
  3. dis[1]=0; //起点
  4. node2 now;
  5. priority_queue<node2>q;
  6. q.push(node2(1,0)); //因为前面有构造函数,所以此处可以直接写node2(1,0)
  7. //1表示的现在的点,0是距离
  8. while(!q.empty())
  9. {
  10. int i;
  11. now=q.top();
  12. q.pop();
  13. if(vis[now.id]==1) continue;
  14. vis[now.id]=1; //选取没有标记的点放入另一个集合中,然后标记它
  15. for(i=pos[now.id];i!=-1;i=a[i].next) //与上一个相同,找它相连的其他未标记的点
  16. {
  17. if(vis[a[i].en]==0&&dis[a[i].en]>dis[now.id]+a[i].val) //松弛操作
  18. {
  19. dis[a[i].en]=dis[now.id]+a[i].val;
  20. q.push(node2(a[i].en,dis[a[i].en]));
  21. }
  22. }
  23. }
  24. }
  1. #include<stdio.h>
  2. #include<queue>
  3. #include<string.h>
  4. using namespace std;
  5. int n,m,vis[111],num,pos[111],dis[111];
  6. struct node1
  7. {
  8. int en,val,next;
  9. }a[100005];
  10. struct node2
  11. {
  12. int id,val; //id是位置
  13. node2(int id1=0,int val1=0) //构造函数
  14. {
  15. id=id1;val=val1;
  16. }
  17. friend bool operator <(node2 x,node2 y) //重载<符号
  18. {
  19. return x.val>y.val;
  20. }
  21. };
  22. void add(int st,int en,int val)
  23. {
  24. a[num].en=en;
  25. a[num].val=val;
  26. a[num].next=pos[st];
  27. pos[st]=num;
  28. num++;
  29. }
  30. void dij()
  31. {
  32. dis[1]=0;
  33. node2 now;
  34. priority_queue<node2>q;
  35. q.push(node2(1,0));
  36. while(!q.empty())
  37. {
  38. int i;
  39. now=q.top();
  40. q.pop();
  41. if(vis[now.id]==1) continue; //该点走过
  42. vis[now.id]=1;
  43. for(i=pos[now.id];i!=-1;i=a[i].next)
  44. {
  45. if(dis[a[i].en]>dis[now.id]+a[i].val)
  46. {
  47. dis[a[i].en]=dis[now.id]+a[i].val;
  48. q.push(node2(a[i].en,dis[a[i].en]));
  49. }
  50. }
  51. }
  52. }
  53. int main()
  54. {
  55. int a,b,c;
  56. while(scanf("%d%d",&n,&m),n+m)
  57. {
  58. num=0;
  59. memset(dis,127,sizeof(dis));
  60. memset(vis,0,sizeof(vis));
  61. memset(pos,-1,sizeof(pos));
  62. while(m--)
  63. {
  64. scanf("%d%d%d",&a,&b,&c);
  65. add(a,b,c);
  66. add(b,a,c);
  67. }
  68. dij();
  69. printf("%d\n",dis[n]);
  70. }
  71. return 0;
  72. }

vector+优先队列优化

vector是一种容器,其实就相当于数组,里面自带有许多函数(但是我不会用 而且觉得自己没有学过C++更不会STL),比通过数组实现的邻接矩阵更容易理解,但是貌似调用vector里面的函数时间复杂度更高一点。

  1. while(m--)
  2. {
  3. scanf("%d%d%d",&a,&b,&c);
  4. v[a].push_back(node(b,c));
  5. v[b].push_back(node(a,c));
  6. //起点a,终点b,时间c存入vector,起点b终点a时间c存入
  7. }
  1. struct node
  2. {
  3. int en,val; //en是目标点,val是到该点的时间
  4. node(int en1=0,int val1=0) //构造函数,然后就可以在下面直接写node(a,b)
  5. {
  6. en=en1;val=val1;
  7. }
  8. friend bool operator <(node x,node y) //重载<符号
  9. {
  10. return x.val>y.val;
  11. }
  12. };
  1. void dij()
  2. {
  3. dis[1]=0;//起点
  4. priority_queue<node>q; //优先队列优化,每次弹出时间最短的
  5. q.push(node(1,dis[1])); //压入起点和dis
  6. while(!q.empty())
  7. {
  8. node now,next;
  9. now=q.top();
  10. q.pop();
  11. if(vis[now.en]==1)
  12. continue;
  13. vis[now.en]=1; //选取没有标记的点放入另一个集合中,然后标记它
  14. for(int i=0;i<v[now.en].size();i++)
  15. {
  16. next=v[now.en][i]; //!!开了vector[11111]貌似相当于一个二维的数组,但是不会用…然后去看了别人怎么写的
  17. if(dis[next.en]>now.val+next.val) //松弛操作
  18. {
  19. dis[next.en]=now.val+next.val;
  20. q.push(node(next.en,dis[next.en]));
  21. }
  22. }
  23. }
  24. }
  1. #include<stdio.h>
  2. #include<queue>
  3. #include<string.h>
  4. #include<vector>
  5. #define INF 1e9
  6. using namespace std;
  7. int n,m,vis[111],dis[111];
  8. struct node
  9. {
  10. int en,val; //id是位置
  11. node(int en1=0,int val1=0) //构造函数= =然后就可以在下面直接写node(a,b)
  12. {
  13. en=en1;val=val1;
  14. }
  15. friend bool operator <(node x,node y) //重载<
  16. {
  17. return x.val>y.val;
  18. }
  19. };
  20. vector<node> v[11111]; //vector的编号表示起点,node中存终点和到终点的时间
  21. void dij()
  22. {
  23. dis[1]=0;//起点
  24. priority_queue<node>q; //优先队列优化,每次弹出时间最短的
  25. q.push(node(1,dis[1]));
  26. while(!q.empty())
  27. {
  28. node now,next;
  29. now=q.top();
  30. q.pop();
  31. if(vis[now.en]==1)
  32. continue;
  33. vis[now.en]=1;
  34. for(int i=0;i<v[now.en].size();i++)
  35. {
  36. next=v[now.en][i];
  37. if(dis[next.en]>now.val+next.val)
  38. {
  39. dis[next.en]=now.val+next.val;
  40. q.push(node(next.en,dis[next.en]));
  41. }
  42. }
  43. }
  44. }
  45. int main()
  46. {
  47. int a,b,c;
  48. while(scanf("%d%d",&n,&m),n+m)
  49. {
  50. memset(dis,127,sizeof(dis));
  51. memset(vis,0,sizeof(vis));
  52. while(m--)
  53. {
  54. scanf("%d%d%d",&a,&b,&c);
  55. v[a].push_back(node(b,c));
  56. v[b].push_back(node(a,c));
  57. //起点a,终点b,时间c存入vector,起点b终点a时间c存入
  58. }
  59. dij();
  60. printf("%d\n",dis[n]);
  61. for(int i=0;i<11111;i++)
  62. v[i].clear();
  63. }
  64. return 0;
  65. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注