首页 > 代码库 > 3371 【模板】单源最短路径

3371 【模板】单源最短路径

2024-08-18 12:29:30   219人阅读

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

 

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 using namespace std;
 5 struct edge{
 6     int k;//终点 
 7     int w;//边权 
 8     //node(int kk, int ww):k(kk), w(ww){}
 9 };
10 bool operator <(const edge&n1, const edge&n2){
11     return n1.w>n2.w;
12 }
13 priority_queue<edge>pq;
14 vector<vector<edge> >v;
15 const int inf = 2147483647;
16 bool used[10010];
17 int d[10010];
18 
19 int main(){
20     int n, m, s;
21     cin>>n>>m>>s;
22     v.clear();
23     v.resize(m+1);
24     int i, j;
25     edge p;//(0, 0);
26     for(i = 1; i <= m; i++){
27         int a, b, c;
28         cin>>a>>b>>c;
29         p.k = b;
30         p.w = c;
31         v[a].push_back(p);
32     }
33     for(i = 1; i <= n; i++) d[i] = inf;
34     d[s] = 0;
35     p.k = s;
36     p.w = 0;
37     pq.push(p);
38     while(!pq.empty()){
39         p = pq.top();
40         pq.pop();
41         if(used[p.k])//已经求出了最短路 
42             continue;
43         used[p.k] = true;
44         d[p.k] = p.w;
45         for(i = 0; i < v[p.k].size(); i++){
46             edge q;
47             q.k = v[p.k][i].k;
48             if(!used[q.k]&&d[q.k]>p.w+v[p.k][i].w){
49                 q.w = p.w + v[p.k][i].w;
50                 pq.push(q);
51             }
52         } 
53     } 
54     for(i=1; i<=n; i++)
55         cout<<d[i]<<" ";
56     return 0;
57 }

备注：

技术分享

加堆优化的dijkstra模板。开始是照着gw的ppt写的，然后瞪了一个小时也没看懂for循环里面那几行，已经觉得人生绝望了。zmj帮我把程序改成了现在这样便于理解的状态，现在我要继续解析一下，边写边想。

用vector<vector<edge>>存图，结构体表示一条边，元素包括边权和终点编号。d[i]表示从源点到编号为i的点的最短距离。

首先把源点push进堆。然后进入while循环。

加堆是如何实现优化的呢？就是因为堆顶元素自动就是最近的元素。

取堆顶元素p（按照定义，这时p边所连的点p.k是堆里w最小，即距离“已选点集”最近的点），将p弹出（必须现在弹出，不能松弛完了再弹）。如果发现p.k是已经用过的点了，则跳过。如果是一个新的点，则将其标记。（pop出的点集就是“已选点集，他们全都used过了）

哎呀，写出来果然清楚多了。因为现在p.k是距离已选点集最近的点，所以它的d值其实已经确定了，于是更新（现在的d就是最终结果）。事实上现在p.k已经是我们选中的点了（即加入点集），接下来做的就是松弛跟它相连的点。

依次遍历与p.k相连的点，即q.k，如果q.k没有用过，并且d值比新路径大，则更新q.w（为什么不更新d值？因为这时d值还没有确定，当然更新也是可以的，但没这个必要。因为当它弹出去时的w值就是最终的d值，所以在这里只更新q.w就可以了），更新完了就把它push进堆，这样下一轮好直接取堆顶元素。

靠，我现在终于想明白了！为什么gw要那么写。因为d值在这里实际上一直是无穷大啊。所以这句根本是废话。弹出去的时候再更新就直接是最终的结果了啊。

再补充一句，为什么可以不用比较就直接给q.w赋值。因为赋值完了都是要把新q push进堆里的，我们总是取堆里最小的，所以那些不够小的push进去根本就无所谓，到时候就又都原封不动地弹出来了。

这个道理我tm想了一下午。写博客真是有奇效。

好了，我要附上gw的原代码写法了。orz

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 using namespace std;
 5 struct edge{
 6     int k;//终点 
 7     int w;//边权 
 8     //node(int kk, int ww):k(kk), w(ww){}
 9 };
10 bool operator <(const edge&n1, const edge&n2){
11     return n1.w>n2.w;
12 }
13 priority_queue<edge>pq;
14 vector<vector<edge> >v;
15 const int inf = 2147483647;
16 bool used[10010];
17 int d[10010];
18 
19 int main(){
20     int n, m, s;
21     cin>>n>>m>>s;
22     v.clear();
23     v.resize(m+1);
24     int i, j;
25     edge p;//(0, 0);
26     for(i = 1; i <= m; i++){
27         int a, b, c;
28         cin>>a>>b>>c;
29         p.k = b;
30         p.w = c;
31         v[a].push_back(p);
32     }
33     for(i = 1; i <= n; i++) d[i] = inf;
34     d[s] = 0;
35     p.k = s;
36     p.w = 0;
37     pq.push(p);
38     while(!pq.empty()){
39         p = pq.top();
40         pq.pop();
41         if(used[p.k])//已经求出了最短路 
42             continue;
43         used[p.k] = true;
44         d[p.k] = p.w;
45         for(i = 0; i < v[p.k].size(); i++){
46             edge q;
47             q.k = v[p.k][i].k;
48             if(used[q.k])continue;
49             q.w = p.w + v[p.k][i].w;
50             pq.push(q);
51         } 
52     } 
53     for(i=1; i<=n; i++)
54         cout<<d[i]<<" ";
55     return 0;
56 }

相信这一下午没有白费，对dijkstra的理解应该还是很深刻的（这样安慰自己）。

3371 【模板】单源最短路径


联系
我们