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