洛谷P4779——记一次Dijkstra算法的做题经历

本文主要是介绍洛谷P4779——记一次Dijkstra算法的做题经历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

　　l老夫最近数据结构学了Dijkstra算法，就想找一题来练习练习。

　　题目链接：https://www.luogu.com.cn/problem/P4779

　　这是一道Dijkstra算法的模板题，要求源点s到各店的最短路径长并输出。

　　起初，我以为这题很简单，不就是堆优化的Dijkstra算法吗？我就提交了如下代码：

 1 #include <iostream>
 2 #include <queue>
 3 #include <vector>
 4 #include <cstdio>
 5 #define maxn 100010
 6 using namespace std;
 7 struct edge {
 8     int to;//有向边的头
 9     int w;//边权
10 };
11 int dist[maxn];
12 struct cmp {
13     bool operator()(const int &x, const int &y)
14     {
15         return dist[x] > dist[y];
16     }
17 };
18 vector<edge>N[maxn];
19 int n, m, s;
20 
21 void dijkstra()
22 {
23     for (int i = 1; i <= n; i++)
24     {
25         dist[i] = 1000000001;
26     }
27     dist[s] = 0;
28     priority_queue<int>q;
29     q.push(s);
30     int v;
31     while (!q.empty())
32     {
33         v = q.top();
34         q.pop();
35         int x;
36         for (int i = 0; i < N[v].size(); i++)
37         {
38             x = N[v][i].to;
39             if (dist[v]+N[v][i].w<dist[x])
40             {
41                 dist[x] = dist[v] + N[v][i].w;
42                 q.push(x);
43                 
44             }
45         }
46     }
47 }
48 int main()
49 {
50     scanf("%d%d%d", &n, &m, &s);
51     int u;
52     edge e0;
53     for (int i = 1; i <= m; i++)
54     {
55         scanf("%d%d%d", &u, &e0.to, &e0.w);
56         N[u].push_back(e0);
57     }
58     dijkstra();
59     for (int i = 1; i <= n; i++)
60         printf("%d ", dist[i]);
61     return 0;
62 }

然后#1、#6TLE了。

　　既然用了堆优化还能超时，那一定就是需要剪枝。

　　然后，我加了一个vis数组，提交了下面的代码：

 1 #include <iostream>
 2 #include <queue>
 3 #include <vector>
 4 #include <cstdio>
 5 #define maxn 100010
 6 using namespace std;
 7 struct edge {
 8     int to;//有向边的头
 9     int w;//边权
10 };
11 int dist[maxn],vis[maxn];
12 struct cmp {
13     bool operator()(const int &x, const int &y)
14     {
15         return dist[x] > dist[y];
16     }
17 };
18 vector<edge>N[maxn];
19 int n, m, s;
20 
21 void dijkstra()
22 {
23     for (int i = 1; i <= n; i++)
24     {
25         dist[i] = 1000000001;
26     }
27     dist[s] = 0;
28     
29     priority_queue<int>q;
30     q.push(s);
31     int v;
32     while (!q.empty())
33     {
34         v = q.top();
35         q.pop();
36         //printf("%d\n", v);
37         if (vis[v])
38             continue;
39         vis[v] = 1;
40         
41         int x;
42         for (int i = 0; i < N[v].size(); i++)
43         {
44             x = N[v][i].to;
45             
46             if (dist[v]+N[v][i].w<dist[x])
47             {
48                 dist[x] = dist[v] + N[v][i].w;
49                 q.push(x);
50             }
51         }
52     }
53 }
54 int main()
55 {
56     scanf("%d%d%d", &n, &m, &s);
57     int u;
58     edge e0;
59     for (int i = 1; i <= m; i++)
60     {
61         scanf("%d%d%d", &u, &e0.to, &e0.w);
62         N[u].push_back(e0);
63     }
64     dijkstra();
65     for (int i = 1; i <= n; i++)
66         printf("%d ", dist[i]);
67     return 0;
68 }

然后WA了4个点。

　　这就说明，这个枝剪得有问题。原因在于，我上面这段代码里，每当一个节点从优先队列里出来时，其vis[]为0的邻接节点都会被打上标记、更新dist[]并入队。设其中某个节点为x，则它必然在未来的某个时间点出队并更新其邻接节点；然而，此时dist[x]未必是s到x路径中的最小值，因此，由x更新的它的邻接节点的dist值就可能不是最小值。而由于vis[x]==1，故以后都不可能再由x对其邻接节点进行更新，这就可能导致错误。

　　于是，我就改变了剪枝的方法。设v为u的邻接节点，对u进行扩展时，用pair<int,int>将v和u、v之间的边权dis一起放入堆中。当v出队时，比较dis和dist[v]，若dis<dist[v]则进行扩展，否则就continue，因为在dis>=dist[v]时的扩展操作不会对结果产生影响。代码如下：

 1 #include <iostream>
 2 #include <queue>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <string>
 6 #define maxn 100010
 7 using namespace std;
 8 typedef pair<int, int> my_pair;//stl在Linux下不支持嵌套，所以用typedef将其重新定义为一个数据类型
 9 struct edge {
10     int to;//有向边的头
11     int w;//边权
12 };
13 int dist[maxn];
14 int vis[maxn];
15 vector<edge>N[maxn];
16 int n, m, s;
17 priority_queue<my_pair>pq;
18 void dijkstra()
19 {
20     for (int i = 1; i <= n; i++)
21     {
22         dist[i] = 1000000000+7;
23         
24     }
25     dist[s] = 0;
26     
27     pq.push(my_pair(-dist[s],s));
28     int u, dis, v;
29     while (!pq.empty())
30     {
31         u = pq.top().second;
32         dis = -pq.top().first;
33         pq.pop();
34         if (dis > dist[u])
35             continue;
36         for (int i = 0; i < N[u].size(); i++)
37         {
38             v = N[u][i].to;
39             if (dist[u] + N[u][i].w < dist[v])
40             {
41                 dist[v] = dist[u] + N[u][i].w;
42                 pq.push(my_pair(-dist[v], v));
43             }
44         }
45     }
46 }
47 int main()
48 {
49     scanf("%d%d%d", &n, &m, &s);
50     int u;
51     edge e0;
52     for (int i = 1; i <= m; i++)
53     {
54         scanf("%d%d%d", &u, &e0.to, &e0.w);
55         N[u].push_back(e0);
56     }
57     dijkstra();
58     for (int i = 1; i <= n; i++)
59         printf("%d ", dist[i]);
60     return 0;
61 }

这篇关于洛谷P4779——记一次Dijkstra算法的做题经历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！