0016:单源最短路径(dijkstra算法)
2024-10-20 20:52:26
题目链接:https://www.luogu.com.cn/problem/P4779
题目描述:给定一个 n 个点,m 条有向边的带非负权图,计算从 s 出发,到每个点的距离。
这道题就是一个单源最短路径的模板,有两种做法:
1.Floyd算法
暴力枚举出所有起点、终点以及中间值,然后算出每两个点间的最小值。
但这个算法时间复杂度较高,是O(n^3),很容易爆掉,在这道题甚至拿不到分。
代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int arr[10000][10000];
4 int main(){
5 int n,m,s,i,j,k,a,b,c;
6 cin>>n>>m>>s;
7 for(i=1;i<=n;i++){
8 for(j=1;j<=n;j++){
9 if(i==j){
10 arr[i][j]=0;
11 }else{
12 arr[i][j]=99999999;
13 }
14 }
15 }
16 while(m--){
17 cin>>a>>b>>c;
18 arr[a][b]=min(c,arr[a][b]);
19 }
20 for(k=1;k<=n;k++){
21 for(i=1;i<=n;i++){
22 if(i==k||arr[i][k]==99999999){
23 continue;
24 }
25 for(j=1;j<=n;j++){
26 arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
27 }
28 }
29 }
30 for(i=1;i<=n;i++){
31 cout<<arr[s][i]<<" ";
32 }
33 }
这道题我们要用一种更高级的算法——
2.dijkstra算法
在无负权边的情况下,时间复杂度为 O(n log n)基本可以顺利通过所有模板题。
先确定初始点到其他所有点的路径(可能为无穷),然后从和该点距离最小点开始遍历,不断更新这些点与初始点的最小距离(学术名叫松弛),最后求出初始点与所有其他点的最短路。
然后要通过此题,还需要前向星存边和优先队列(堆)优化,可能比较难理解,自己画图模拟即可。
上代码(有注释):
1 #include<bits/stdc++.h>
2 using namespace std;
3 long long vis[100001]={0},head[100001],dis[100001],cnt,n,m,s,a,b,c;
4 long long INF=2147483647;//2的31次方,可以看做无穷
5 struct Q{
6 int a,b,c,next;
7 };//邻接表,在有向图中存储起点、终点权值,next用来前向星存边
8 struct node{//放进优先队列中的结构体
9 int w,now;//w为最短路,now为点
10 bool operator <(const node &x)const{
11 return w>x.w;//权值从大到小排
12 }
13 };
14 priority_queue<node> q;//优先队列
15 Q e[500001];
16 void add(int a,int b,int c){//前向星存边
17 e[cnt++].a=a;
18 e[cnt].b=b;
19 e[cnt].c=c;
20 e[cnt].next=head[a];//next存储上一个cnt值,方便for循环从后往前遍历边
21 head[a]=cnt;
22 }
23 void dijkstra(){
24 for(int i=1;i<=n;i++){
25 dis[i]=INF;
26 }
27 dis[s]=0;
28 q.push((node){0,s});//将起点压入队列
29 while(!q.empty()){//队列非空
30 node x=q.top();//弹出堆顶(最小)元素
31 q.pop();
32 int u=x.now;
33 if(vis[u]==1){
34 continue;//遍历完无需再遍历
35 }
36 vis[u]=1;
37 for(int i=head[u];i;i=e[i].next){//用前向星遍历
38 int v=e[i].b;
39 dis[v]=min(dis[v],dis[u]+e[i].c);//松弛操作
40 q.push((node){dis[v],v});
41 }
42 }
43 }
44 int main(){
45 cin>>n>>m>>s;
46 for(int i=0;i<m;i++){
47 cin>>a>>b>>c;
48 add(a,b,c);
49 }
50 dijkstra();
51 for(int i=1;i<=n;i++){
52 cout<<dis[i]<<" ";
53 }
54 }
最新文章
- Android Studio导入第三方类库的方法(转)
- python2.7安装matplotlib遇到的问题及解决方法
- js中各种跨域问题实战小结(二)
- java抓取快递信息
- wego微购RSS、Sitemap、Ping、腾讯拍拍网购采集插件
- Foundation框架—集合
- Python - 多版本共存与虚拟独立环境
- CUBRID学习笔记 10 数据库文件的类型和含义
- 关于C语言和汇编语言相互嵌套调用
- scjp考试准备 - 5 - 重载和重写
- c#md5与SHA1验证函数
- 初识pngdrive
- poj2387(最短路)
- IE支持CSS3圆角
- Java ZIP压缩和解压缩文件并兼容linux
- Makefile持续学习二
- eclipse生成【带有外部jar包】的java可执行jar包
- 【BZOJ2818】Gcd(莫比乌斯反演)
- Thinking in Java Chapter 13
- Tensorflow检验GPU是否安装成功 及 使用GPU训练注意事项