40 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], q[maxn];

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 dijkstra()

{

for ( int i = 2; i <= n; ++i )

d[i] = inf;

int min, pmin = 0;

for ( int i = 1; i <= n; ++i )

{

min = inf;

for ( int j = 1; j <= n; ++j )

if ( d[j] < min && !q[j] )

min = d[j], pmin = j;

q[pmin] = 1;

graf *t = a[pmin];

while ( t )

{

if ( d[ t->nod ] > d[pmin] + t->cost )

d[ t->nod ] = d[pmin] + t->cost;

t = t->next;

}

}

}

int main()

{

read();

dijkstra();

for ( int i = 2; i <= n; ++i )

fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);

fprintf(out, "\n");

return 0;

}