最短路

单源最短路径例题：P3371 P4779

Dijkstra

求解非负权图上单源最短路径

时间复杂度： $O(n^2+m)$

# include<iostream>
# include<vector>
using namespace std;

struct edge{
	int v,w;
};

const int N=1e5+5,inf=0x7fffffff; 
int n,m,s,x,y,z;
int dis[N],cnt[N];
bool vis[N];
vector<edge> e[N];

void add(int x,int y,int z){
	e[x].push_back({y,z});
	++cnt[x];
}

void dijkstra(){
	for(int i=1;i<=n;++i) dis[i]=inf;
	dis[s]=0;
	for(int i=0;i<n;++i){
		int u=0,md=inf;
		for(int j=1;j<=n;++j)
			if(!vis[j]&&dis[j]<inf) u=j;
		vis[u]=1;
		for(int j=0;j<cnt[u];++j){
			int v=e[u][j].v,w=e[u][j].w;
			if(dis[u]+w<dis[v])
				dis[v]=dis[u]+w;
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=0;i<m;++i){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra();
	for(int i=1;i<=n;++i) cout<<dis[i]<<" ";
	return 0;
}

堆优化

用优先队列对Dijkstra算法进行优化

时间复杂度： $O(m \log m)$

# include<iostream>
# include<queue>
# include<vector>
# include<map>
using namespace std;
# define m(a,b) make_pair(a,b)
# define p pair<int,int>

struct edge{
	int v,w;
};

const int N=1e5+5,inf=0x7fffffff; 
int n,m,s,x,y,z;
int dis[N],cnt[N];
bool vis[N];
vector<edge> e[N];
priority_queue<p,vector<p>,greater<p> > q;

void add(int x,int y,int z){
	e[x].push_back({y,z});
	++cnt[x];
}

void dijkstra(){
	for(int i=1;i<=n;++i) dis[i]=inf;
	dis[s]=0;
	q.push(m(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<cnt[u];++i){
			int v=e[u][i].v,w=e[u][i].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push(m(dis[v],v));
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=0;i<m;++i){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra();
	for(int i=1;i<=n;++i) cout<<dis[i]<<" ";
	return 0;
}

SPFA

可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断

时间复杂度： $O(nm)$

# include<iostream>
# include<vector>
# include<queue>
# include<map>
using namespace std;
# define ll long long
# define p pair<ll,int>
# define m(a,b) make_pair(a,b)

const int N=1e4+5;
const ll inf=0x7fffffff;
int n,m,s,u,v,w;
vector<p> e[N];
ll dis[N];
bool vis[N];
queue<int> q;

void spfa(){
	dis[s]=0;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0,l=e[u].size();i<l;++i){
			v=e[u][i].second;
			w=e[u][i].first;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}

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

判断负环

# include<iostream>
# include<vector>
# include<queue>
# include<map>
using namespace std;
# define ll long long
# define p pair<ll,int>
# define m(a,b) make_pair(a,b)

const int N=2e3+5;
const ll inf=0x7fffffff;
int t,n,m,u,v,cnt[N];
vector<p> e[N];
ll w,dis[N];
bool vis[N];
queue<int> q;

void add(int u,int v,ll w){
	e[u].push_back(m(w,v));
}

bool spfa(){
	q.push(1);
	dis[1]=0;
	vis[1]=1;
	while(!q.empty()){
		u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0,l=e[u].size();i<l;++i){
			v=e[u][i].second;
			w=e[u][i].first;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n) return 0;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				} 
			}
		}
	}
	return 1;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) dis[i]=inf;
	for(int i=1;i<=m;++i){
		cin>>u>>v>>w;
		add(u,v,w);
		if(w>=0) add(v,u,w);
	}
	if(spfa()) cout<<"NO\n";
	else cout<<"YES\n";
	return 0;
}

杂项

分层图

例题 P4822

# include<iostream>
# include<vector>
# include<queue>
# include<map>
using namespace std;
# define ll long long
# define p pair<ll,int> //距离，点 
# define m(a,b) make_pair(a,b)
# define d first
# define node second

const int N=55,K=51;
const ll inf=1e9+5;
int n,m,k,s,t,a,b;
ll dis[N*K],c,ans=inf;
bool vis[N*K];
vector<p> e[N*K];
priority_queue<p,vector<p>,greater<p> > q;

void add(int a,int b,ll c){
	for(int i=0;i<=k;++i){
		int u=a+i*n,v=b+i*n;
		e[u].push_back(m(c,v));
		if(i!=k) e[u].push_back(m(c/2,v+n));
	}
}

void dijkstra(){
	for(int i=0;i<=k;++i)
		for(int j=1;j<=n;++j)
			dis[j+i*n]=inf;
	dis[s]=0;
	q.push(m(0,s));
	while(!q.empty()){
		int u=q.top().node;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0,l=e[u].size();i<l;++i){
			int v=e[u][i].node;
			ll w=e[u][i].d;
			if(dis[v]>=dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(m(dis[v],v));
			}
		}
	}
}

int main(){
	cin>>n>>m>>k;
	s=1,t=n;
	for(int i=1;i<=m;++i){
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	dijkstra();
	for(int i=0;i<=k;++i)
		ans=min(ans,dis[t+n*i]);
	cout<<ans;
	return 0;
}