Cod sursa(job #186721)
#include<stdio.h>
using namespace std;
typedef struct nod{
long info;
long dist;
nod *next;
}*pnod;
pnod prim[50002],pp;
long int n,m,i,a,b,c,h[50002],ph[50002],d[50002],i8,lh,nv,viz[50002],dv,nn,dn,aux;
void add(pnod &p,long j,long c);
void read();
void hd(long int ic);
void hu(long int ic);
void sh(long int i1,long int i2);
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
read();
i8=1000000000;
for(i=1;i<=n;i++){
h[i]=i;
ph[i]=i;
d[i]=i8;
}
d[1]=0;
lh=n;
while(lh && d[h[1]]<i8){
nv=h[1];
viz[nv]=1;
dv=d[nv];
h[1]=h[lh];
ph[h[1]]=1;
lh--;
hd(1);
pp=prim[nv];
while(pp){
if(viz[pp->info])
pp=pp->next;
else{
if(d[pp->info]>dv+pp->dist){
d[pp->info]=dv+pp->dist;
hu(ph[pp->info]);
}
pp=pp->next;
}
}
}
for(i=2;i<=n;i++){
if(d[i]==i8)
d[i]=0;
printf("%ld ",d[i]);
}
printf("\n");
fcloseall();
return 0;
}
void add(pnod &p,long j,long c)
{
nod *q=new nod;
q->info=b;
q->dist=c;
q->next=p;
p=q;
}
void read()
{
scanf("%ld %ld",&n,&m);
for(i=1;i<=m;i++){
scanf("%ld %ld %ld",&a,&b,&c);
add(prim[a],b,c);
}
}
void hd(long int ic)
{
long int is,is1;
is=ic<<1;
is1=is|1;
if(is>lh)
return;
if(is<lh)
if(d[h[is1]]<d[h[is]])
is=is1;
if(d[h[is]]<d[h[ic]]){
sh(is,ic);
hd(is);
}
}
void hu(long int ic)
{
long int is;
is=ic>>1;
if(!is)
return;
if(d[h[is]]>d[h[ic]]){
sh(is,ic);
hu(is);
}
}
void sh(long int i1,long int i2)
{
aux=h[i1];
h[i1]=h[i2];
h[i2]=aux;
ph[h[i1]]=i1;
ph[h[i2]]=i2;
}