dijkstra60分#2#9#10TLE#3WA求条

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int M=2e5+4;
int n,m,s;
int head[M],idx;
int dis[M],vis[M];

struct Node{
	int u,v,w,next;
}eg[M];

typedef pair<int ,int> p;

void add(int u,int v,int w){
	idx++;
	eg[idx]={u,v,w,head[u]};
	head[u]=idx;
}

void dijkstra(int s){
	priority_queue<p,vector<p>,greater<p> > q;
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int v=q.top().second;
		int w=q.top().first;
		q.pop();
		
		if(vis[v]==1){
			continue;
		}
		vis[v]=1;
		for(int i=head[v];i>=1;i=eg[i].next){
			int v2=eg[i].v;
			if(dis[v2]>dis[v]+eg[i].w){
				dis[v2]=dis[v]+eg[i].w;
				q.push({dis[v2],v2});
			}
		}
	}
}
int main(){
	int u,v,w;
	cin>>n>>m>>s;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}