堆优化的 dijkstra，链式前向星存图，开 O2 优化也是如此

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m,u,v,w,d[200001],tot,head[200001],s;
bool vis[200001];
struct edge{
	int u,v,w,next;
}g[200001];
struct point{
	int id,d;
	bool operator<(point a)const{
		return d>a.d;
	}
};
priority_queue<point> q;
void addedge(int u,int v,int w){
	g[++tot].u=u;
	g[tot].v=v;
	g[tot].next=head[u];
	g[tot].w=w;
	head[u]=tot;
	return;
}
void dijkstra(int x){
	memset(d,127,sizeof(d));
	d[x]=0;
	q.push((point){x,0});
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		vis[u]=1;
		for(int i=head[u];i!=-1;i=g[i].next){
			int v=g[i].v;
			int w=g[i].w;
			if(vis[v])continue;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				q.push((point){v,d[v]});
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m>>s;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		addedge(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<d[i]<<" ";
	}
	return 0;
}