首页 > 编程语言 >最短路算法

最短路算法

时间:2023-06-25 21:48:15浏览次数:43  
标签:ch 短路 second long 算法 include

目录

最短路算法

单源最短路-迪杰斯特拉算法

用于计算一个节点到其他所有节点的最短路径
Dijkstra 算法是贪心算法, 是一种求解非负权图上单源最短路径的算法。
基本思想是:设置一个顶点的集合S,并不断地扩充这个集合,当且仅当从源点到某个点的路径已求出时它才属于集合S。开始时S中仅有源点,调整S 集合之外的点的最短路径长度, 并从中找到当前最短路径点,将其加入到集合S,直到所有的点都在S中。
目前仅对非负权边图有效
例题:

  1. 【模板】单源最短路径(标准版)
//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
typedef std::pair<ull,ull> pull;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;

const int maxm=2e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,m,s,head[maxm],cnt,dis[maxm];
bool vis[maxm];
struct node{
	ll to,next,wei;
}p[maxm];

void add_edge(ll u,ll v, ll w){
	p[cnt].to=v;
	p[cnt].next=head[u];
	p[cnt].wei=w;
	head[u]=cnt++;
	return ;
}

void pre(int x){
	for(int i=1;i<=x;++i){
		dis[i]=inf;
		head[i]=-1;
		vis[i]=false;
	}
	return ;
}

void dij(int x){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
	q.push({0,x});
	pair<ll,ll> t;
	while(!q.empty()){
		t=q.top();
		q.pop();
		if(vis[t.second]) continue;
		vis[t.second]=true;
		dis[t.second]=t.first;
		for(int i=head[t.second];i!=-1;i=p[i].next){
			if(!vis[p[i].to]&&dis[t.second]+p[i].wei<dis[p[i].to]){
				q.push({dis[t.second]+p[i].wei,p[i].to});
			}
		}
	}
	return ;
}

void solve(){
	cnt=0;
	cin>>n>>m>>s;
	pre(n);
	for(int i=0;i<m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	dij(s);
	for(int i=1;i<=n;++i){
		cout<<dis[i]<<" \n"[i==n];
	}
	return ;
}

signed main(){
	// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

标签:ch,短路,second,long,算法,include
From: https://www.cnblogs.com/Qiansui/p/17503993.html

相关文章

  • 对算法的一些理解
    主要的算法思路有这几个:1、穷举2、动态规划3、分治4、贪心5、回溯6、分支限界这些算法思路之间是有区别和联系的。但是,很多文章没有把他们的区别和联系讲出来,这里尝试梳理一下。穷举是最朴素、最原始的思路。穷举就是把所有的可能一个一个列举出来,逐个分析后,再合并分析后......
  • 文心一言 VS 讯飞星火 VS chatgpt (47)-- 算法导论6.1 5题
    五、一个已排好序的数组是一个最小堆吗?文心一言:一个已排好序的数组不一定是一个最小堆。最小堆是一种特殊的二叉树,它满足以下性质:对于任意节点x,其父节点y的值都小于等于x的值。而一个已排好序的数组只是一个有序数组,它满足任意的元素都是按从小到大的顺序排列的,但并不一定满......
  • 文心一言 VS 讯飞星火 VS chatgpt (47)-- 算法导论6.1 5题
    五、一个已排好序的数组是一个最小堆吗?文心一言:一个已排好序的数组不一定是一个最小堆。最小堆是一种特殊的二叉树,它满足以下性质:对于任意节点x,其父节点y的值都小于等于x的值。而一个已排好序的数组只是一个有序数组,它满足任意的元素都是按从小到大的顺序排列的,但并不一定......
  • 24.贪心算法.
    贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。请看下面案例,假设有如下课程,希望尽可能多的将课程安排在一间教室里:课程开始时间结束时间美术9:0010:00英语9:3010:30......
  • 3.数据结构与算法复习--线性表
    线性表的定义和特点线性表是具有相同特性的数据元素的一个有限序列(a1,a2,..ai-1,ai,ai+1,...an)a1:线性起点ai-1为ai的直接前驱,ai+1为ai的直接后驱an为线性终点,当n=0时称为空表线性表同一线性表中的元素必定具有相同特性,数据元素间的关系时线性关系线性表的逻辑特征是:......
  • 基于多算法融合的啸叫抑制方案总结
    前记 在对讲和本地扩音领域,啸叫抑制是一个无法绕过去的话题。怎么抑制啸叫是一个非常棘手的问题。笔者及团队在这个方向研究了好久。终于取得了一些阶段性的进展。这里做一下梳理。 心路历程 刚开始想依靠单纯的算法去解决。做了很多仿真,发现都不是很理想。不是抑制太狠了......
  • 【算法】罗马数字与整型数字转换,数值范围1-4000
    编写两个函数,将罗马数字与整数值进行转换。每个函数将测试多个罗马数字值。现代罗马数字是通过从最左边的数字开始分别表示每个数字,并跳过任何值为零的数字来书写的。在罗马数字1990中,表示为:1000=M,900=CM,90=XC;从而产生MCMXC。2008被写成2000=MM,8=VIII;或MMVIII。1666年,每一个罗马......
  • 反向传播算法的理解
    反向传播算法--求偏导速度大大提升(一次求解)https://zhuanlan.zhihu.com/p/250816711用计算图来解释几种求导方法:1.1计算图式子e=(a+b)∗(b+1) 可以用如下计算图表达:令a=2,b=1则有:      所以上面的求导方法总结为一句话就是:路径上所有边相乘,所有......
  • 22.回溯算法
    1.回溯的基本原理  在问题的解空间中,按深度优先遍历策略,从根节点出发搜索解空间树。算法搜索至解空间的任意一个节点时,先判断该节点是否包含问题的解。如果确定不包含,跳过对以该节点为根的子树的搜索,逐层向其祖先节点回溯,否则进入该子树,继续深度优先搜索。  回溯法解问题的......
  • abc061d <单源最短路, spfa, 判断负环>
    D-ScoreAttack//https://atcoder.jp/contests/abc061/tasks/abc061_d//单源最短(长)路,spfa,判断负(正)环//本题是找最长的路径,实际上取个负号即可//注意,找到一个负环不能直接结束,只能进行标记cyc[]#include<iostream>#include<algorithm>#include<vect......