HDU 2544最短路【dijkstra 链式前向星+优先队列优化】

最开始学最短路的时候只会用map二维数组存图,那个时候还不知道这就是矩阵存图,也不懂得效率怎么样

经过几个月的历练再回头看最短路的题, 发现图可以用链式前向星来存, 链式前向星的效率是比较高的。对于查找边,可以用优先队列来优化查找速度,两者结合可以提高很高的效率.

写这篇博客是为了给自己提供一个模板, 在自己研究这问题的时候发生了很多, 有一些小细节的错误错的我怀疑人生, 其实还是自己太菜了,包括函数的重载也不懂, 就琢磨了好久

题目链接：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条商店到赛场的路线。

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

Sample Input

2 1

1 2

3 3

3 1

2 5

2 3

5 3

1 2

0 0

Sample Output

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 const int inf = 0x3f3f3f3f;
 5 using namespace std;
 6 
 7 int head[110], cnt;
 8 int dis[110], vis[110];
 9 
10 struct Edge //链式前向星 
11 {
12     int next, to, val;
13 }edge[10000 * 2];
14 
15 void add(int a, int b, int c)
16 {
17     edge[++ cnt].to = b;
18     edge[cnt].val = c;
19     edge[cnt].next = head[a];
20     head[a] = cnt;
21 }
22 
23 struct Node
24 {
25     int pot, dis;//pot为某点, dis为源点到pot点的距离 
26     bool operator < (const Node &a)const  //这里就是优先队列的写法 
27     {
28         return dis > a.dis;
29     }
30 }node;
31 
32 void dij()
33 {
34     memset(vis, 0, sizeof(vis));  
35     memset(dis, inf, sizeof(dis));
36     dis[1] = 0; //dis[x]
37     priority_queue<Node>Q;
38     node.pot = 1, node.dis = 0; //node.pot = x, node.dis = 0 即改为以x点为源点
39     Q.push(node);
40     while(!Q.empty())
41     {
42         Node a = Q.top();//找出最短的一条路径 
43         Q.pop();
44         if(vis[a.pot])//如果该路径已经被确定过了 就跳过 
45             continue;
46         vis[a.pot] = 1; //如果之前没确定过, 那么这次从队列出来就已经确定了是最短的了 标记 
47         for(int i = head[a.pot]; i != -1; i = edge[i].next)
48         {
49             int to = edge[i].to;
50             if(!vis[to] && dis[to] > dis[a.pot] + edge[i].val) //注意还有 !vis[to] 表示to点没有被确定 如果已经被确定的话就不用参与更新了 
51             {
52                 dis[to] = dis[a.pot] + edge[i].val;
53                 node.dis = dis[to], node.pot = to;
54                 Q.push(node);//更新之后就入队,一直更新下去, 最后队列为空 
55             }
56         }
57     }
58 }
59 
60 int main()
61 {
62     int n, m;
63     while(scanf("%d%d", &n, &m)!=EOF)
64     {
65         if(n == 0 && m == 0)
66             break;
67         memset(head, -1, sizeof(head));  //链式前向星的初始化 
68         cnt = 0;
69         for(int i = 1; i <= m; i ++)
70         {
71             int a, b, c;
72             scanf("%d%d%d", &a, &b, &c);
73             add(a, b, c);  //dij最短路的边一般都是无向边 ,链式前向星要存两条 
74             add(b, a, c);
75         }
76         dij();
77         printf("%d\n", dis[n]);
78     }
79     return 0;
80 }

View Code

HDU 2544最短路 【dijkstra 链式前向星+优先队列优化】

HDU 2544最短路【dijkstra 链式前向星+优先队列优化】