mxqz 最短路板子
查看原帖
mxqz 最短路板子
762775
Crsuh2er0楼主2023/11/3 17:48

这到底是堆优 Dijkstra 还是堆优 SPFA?

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 100010
int n,m,s,dis[MAXN];
struct edge{
	int v,w;
    bool operator>(const edge &tmp)const{
		return w > tmp.w;
	}
};
basic_string<edge> p[MAXN];
priority_queue<edge,basic_string<edge>,greater<edge> > q; 
void Dijkstra(){
	fill(dis,dis + n + 1,INT_MAX);
	q.push({s,dis[s] = 0});
	while(!q.empty()){
		int u = q.top().v,d = q.top().w;
		q.pop();
		if(d != dis[u]) continue;
		for(const auto &[v,w] : p[u]){
			if(dis[v] > LL(dis[u]) + w){
				dis[v] = dis[u] + w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("P4779.in","r",stdin);
	#endif
	cin.tie(0) -> ios::sync_with_stdio(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i = 1,u,v,w;i <= m;i++){
		cin>>u>>v>>w;
		p[u].push_back({v,w});
	}
	Dijkstra();
	for(int i = 1;i <= n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}
2023/11/3 17:48
加载中...