< 娱乐部分 杂物部分 >

单源最短路径 - dijkstra 模板

P4779

请尊重纯手搓艺人

此代码使用 $邻接表$ 存图，输入分别为 $节点数$ 、 $边数$ 与 $开始节点编号$，输出为从 $开始节点$ 到 $每个节点$ 的 $最短路径$

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,dist[100005],par[100005];
bool vis[100005];
struct edge{
	long long to,w;
};
struct node{
	long long id,v;
	bool operator<(const node& other) const {
        return this->v > other.v; 
    }
};
vector<edge> g[100005];
priority_queue<node> q;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		dist[i]=1e18;
		par[i]=-1;
	}
	for(int i=1;i<=m;i++){
		int ru,rv,rw;
		cin>>ru>>rv>>rw;
		g[ru].push_back(edge{rv,rw});
	}
	dist[s]=0;
	q.push(node{s,0});
	while(!q.empty()){
		node rt=q.top();
		q.pop();
		int ri=rt.id;
		if(vis[ri]) continue;
		vis[ri]=true;
		for(int i=0;i<g[ri].size();i++){
			long long fv=g[ri][i].to,fw=g[ri][i].w;
			if(dist[ri]+fw<dist[fv]){
				dist[fv]=dist[ri]+fw;
				q.push(node{fv,dist[fv]});
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dist[i]<<' ';
	}
	return 0;
}

Embarcadero Dev-C++ 6.3最新版下载

Link

https://yyhdown.lanzoum.com/ia9BA3mrxpta

//并查集函数

#include<bits/stdc++.h>
using namespace std;
int find(int fx){
	if(f[fx]==fx) return fx;
	return f[fx]=find(f[fx]);
}
bool check(int cx,int cy){
	return find(cx)==find(cy);
}
void unite(int ux,int uy){
	if(!check(ux,uy)) f[find(ux)]=find(uy);
	return ;
}
int main(){
	return 0;
}

画图网站：