知否？知否？应是绿肥红瘦

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=3e5+5;
const int INF=2147483647;
int n,m,s,idx;
int h[N],w[N],e[N],Next[N];
int dist[N];
bool flag[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,Next[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
	for(int i=0;i<=n;i++)
		dist[i]=INF;
	dist[s]=0;
	pq.push({0,s});
	while(!pq.empty())
	{
		int a=pq.top().first,b=pq.top().second;
		pq.pop();
		if(flag[b]) continue;
		flag[b]=true;
		for(int i=h[b];i!=-1;i=Next[i])
		{
			int c=e[i];
			if(dist[c]>dist[b]+w[i])
			{
				dist[c]=dist[b]+w[i];
				pq.push({dist[c],c});
			}
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d ",dist[i]);
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=0;i<=n;i++)
		h[i]=-1;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	dijkstra(); 
	return 0;
}

另外早就有人问这个问题了

求dalao指教\orz