GF2026提高组-dijkstra(模板代码)

• 导航页

• GF2026C1图的定义、存储和遍历

• GF2026提高组-并查集

……

前言

$dijkstra$模板:

错误

结构体:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=2e5+5;
ll n,m,s,dis[N];
bool vis[N];
vector < pair<int,int> > edge[N];
void dijkstra(int s){
	for(int j=1;j<=n;j++)dis[j]=LONG_LONG_MAX;
	dis[s]=0;
	
	for(int i=2;i<=n;i++){//完成n-1个遍 
		int t=dis[0],u;
		for(int j=1;j<=n;j++){
			if(!vis[j] && t>dis[j]){
				t=dis[j];u=j;
			}
		}
		vis[u]=1;
		//松弛u点 
		for(auto j:edge[u]){
			int v=j.first,w=j.second; // u  ---w--->  v
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
			}
		}		
	}	
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;

	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].push_back(make_pair(v,w));
		
	}
	
	dijkstra(s);
	
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

优先队列优化后:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=2e5+5;
ll n,m,s,dis[N];
bool vis[N];
priority_queue < pair<ll,int> > q;
vector < pair<int,int> > edge[N];
void dijkstra(int s){
	for(int j=1;j<=n;j++)dis[j]=LONG_LONG_MAX;
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto j:edge[u]){
			int v=j.first,w=j.second;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}		
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].push_back(make_pair(v,w));
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}