dijkstra and spfa

spfa

struct Node{
	int w,to,nxt;
}edg[maxn];
int head[maxn],tot;
void add_edge(int u,int w,int v){
	edg[++tot].nxt=head[u];edg[tot].to=v;
	edg[tot].w=w;head[u]=tot;
}
bool vis[maxn];
int cnt[maxn],dis[maxn];
bool spfa(int n,int s){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	queue<int>q;
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();vis[u]=0; 
		for(int i=head[u];i;i=edg[i].nxt){
			int v=edg[i].to,w=edg[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return false;
				if(!vis[v])q.push(v),vis[v]=1;
			}
		}
	}
	return true;
}

dijkstra

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define mkp make_pair
#define int long long
const int maxn=3e5+10;
vector<pii>E[maxn];
int dis[maxn];
bool vis[maxn];
struct node{
	int dis,pos;
	bool operator< (const node &x)const{
		return x.dis<dis;
	}
};
void dijkstra(int s){
	priority_queue<node>q;
	dis[s]=0;
	q.push((node{0,s}));
	while(!q.empty()){
		int u=q.top().pos;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(pii i:E[u]){
			int v=i.fi,w=i.se;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push((node){dis[v],v});
			}
		}
	}
}
void solve(){
	int m,n,s;cin>>n>>m>>s;
	for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		E[u].push_back(mkp(v,w));
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}
signed main(){
	int t;t=1;while(t--){
		solve();
	}
	return 0;
}