Cod sursa(job #627669)
#include<cstdio>
#define inf 1001
using namespace std;
int n, m;
int L[22000][22000];
int dmin[50001], pred[50001];
bool viz[50001];
void Dijkstra(int start)
{
int i, j, minim, poz;
bool gata = false;
for(i = 1; i <= n; i++)
{
dmin[i] = inf;
pred[i] = 0;
viz[i] = false;
}
dmin[start] = pred[start] = 0;
for(i = 1; i <= n && !gata; i++)
{
minim = inf;
for(j = 1; j <= n; j++)
{
if(dmin[j] < minim && !viz[j])
{
minim = dmin[j];
poz = j;
}
}
if(minim == inf) gata = true;
else
{
for(j = 1; j <= n; j++)
{
if(L[poz][j] + dmin[poz] < dmin[j] && L[poz][j] != inf)
{
dmin[j] = L[poz][j] + dmin[poz];
pred[j] = poz;
}
}
viz[poz] = true;
}
}
}
int main()
{
int i, x, y, c;
freopen("dijkstra.in", "r", stdin);
freopen("dijkstra.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 0; i <= n; i++)
for (x = 0; x <= m; x++)
L[i][x] = inf;
for (i = 0; i <= n; i++) L[i][i] = 0;
for(i = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &c);
L[x][y] = c;
}
Dijkstra(1);
for(i = 2; i <= n; i++) printf("%d ", dmin[i]);
return 0;
}