dj+优先队列

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int v,w;
};

int n,m,s,d[100005],vis[100005];
vector<node> G[100005];
pair<int,int> t1,t2;
priority_queue<pair<int,int> > pq;

int main()
{
	cin>>n>>m>>s;
	for (int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		G[a].push_back({b,c});
	}
	memset(d,0x3f,sizeof(d));
	d[s]=0,pq.push({0,s});;
	while (!pq.empty())
	{
		t2=pq.top();
		pq.pop();
		int u=t2.second;
		if (vis[u])	continue;
		vis[u]=1;
		for (int i=0;i<G[u].size();i++)
		{
			int v=G[u][i].v,w=G[u][i].w;
			if (d[v]>d[u]+w)
				d[v]=d[u]+w;
			pq.push({d[v],v});
		}
	}
	for (int i=1;i<=n;i++)
		cout<<d[i]<<" ";
	return 0;
}