100 puncte
#include <cstdio>
const int maxn = 50001;
const int inf = 1 << 30;
FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");
struct graf
{
int nod, cost;
graf *next;
};
int n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;
void add(int where, int what, int cost)
{
graf *q = new graf;
q->nod = what;
q->cost = cost;
q->next = a[where];
a[where] = q;
}
void read()
{
fscanf(in, "%d %d", &n, &m);
int x, y, z;
for ( int i = 1; i <= m; ++i )
{
fscanf(in, "%d %d %d", &x, &y, &z);
add(x, y, z);
}
}
void swap(int x, int y)
{
int t = h[x];
h[x] = h[y];
h[y] = t;
}
void upheap(int what)
{
int tata;
while ( what > 1 )
{
tata = what >> 1;
if ( d[ h[tata] ] > d[ h[what] ] )
{
poz[ h[what] ] = tata;
poz[ h[tata] ] = what;
swap(tata, what);
what = tata;
}
else
what = 1;
}
}
void downheap(int what)
{
int f;
while ( what <= k )
{
f = what;
if ( (what<<1) <= k )
{
f = what << 1;
if ( f + 1 <= k )
if ( d[ h[f + 1] ] < d[ h[f] ] )
++f;
}
else
return;
if ( d[ h[what] ] > d[ h[f] ] )
{
poz[ h[what] ] = f;
poz[ h[f] ] = what;
swap(what, f);
what = f;
}
else
return;
}
}
void dijkstra_heap()
{
for ( int i = 2; i <= n; ++i )
d[i] = inf, poz[i] = -1;
poz[1] = 1;
h[++k] = 1;
while ( k )
{
int min = h[1];
swap(1, k);
poz[ h[1] ] = 1;
--k;
downheap(1);
graf *q = a[min];
while ( q )
{
if ( d[q->nod] > d[min] + q->cost )
{
d[q->nod] = d[min] + q->cost;
if ( poz[q->nod] != -1 )
upheap( poz[q->nod] );
else
{
h[++k] = q->nod;
poz[ h[k] ] = k;
upheap( k );
}
}
q = q->next;
}
}
}
int main()
{
read();
dijkstra_heap();
for ( int i = 2; i <= n; ++i )
fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);
fprintf(out, "\n");
return 0;
}