infoarena informatica de performanta

#include <cstdio>
#include <list>
#include <set>

using namespace std;

int n,m;
int d[50002],inms[50002];

struct Compar{
	bool operator()(int i,int j){
		return d[i]<d[j];
	}
};

list<pair<int,int> > l[50002];
list<pair<int,int> >::iterator it;
multiset<int ,Compar> ms;

void citire(){
	scanf("%d %d",&n,&m);
	int i,x,y,c;
	for(i=1;i<=m;i++){
		scanf("%d %d %d" , &x,&y,&c);
		l[x].push_back(make_pair(y,c));
	}
}

void dijkstra(int rad){
	int i,poz;
	for(i=1;i<=n;i++){
		d[i]=1000000000;
		inms[i]=0;
	}
	inms[rad]=1;
	d[rad]=0;
	ms.insert(rad);
	while(!ms.empty()){
		poz=*ms.begin();
		ms.erase(ms.begin());
		inms[poz]=0;
		for(it=l[poz].begin();it!=l[poz].end();++it)
			if(d[(*it).first]>d[poz]+(*it).second){
				if(inms[(*it).first]==1){
					ms.erase((*it).first);
				}
				else {
					inms[(*it).first]=1;
				}
				d[(*it).first]=d[poz]+(*it).second;
				ms.insert((*it).first);
				
			}
	}
}

void afisare(){
	int i;
	for(i=2;i<=n;i++)
		if(d[i]!=1000000000)
			printf("%d ",d[i]);
		else printf("0 ");
	printf("\n");
}

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	afisare();
	return 0;
}