Cod sursa(job #627658)
#include<cstdio>
#include<vector>
#include<algorithm>
#define inf (1<<30)
using namespace std;
int n, m;
vector <int>L[50001];
vector <int> dmin, pred;
vector <bool> viz;
void Dijkstra(int start)
{
int i, j, minim, poz;
bool gata = false;
for(i = 0; i <= n; i++)
{
dmin.push_back(inf);
pred.push_back(0);
viz.push_back(false);
}
dmin[start] = pred[start] = 0;
for(i = 1; i <= n && !gata; i++)
{
minim = dmin[i];
poz = i;
for(j = 0; j < L[i].size(); j++)
{
int adiacent = L[i][j] / 10000;
int cost = L[i][j] % 10000;
if(cost < minim && !viz[adiacent])
{
minim = cost;
poz = adiacent;
}
}
if(minim == inf) gata = true;
else
{
for(j = 0; j < L[poz].size(); j++)
{
int cost = dmin[poz] + L[poz][j] % 10000;
int adiacent = L[poz][j] / 10000;
if(cost < dmin[adiacent]) dmin[adiacent] = cost;
}
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 = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &c);
L[x].push_back(y * 10000 + c);
}
Dijkstra(1);
for(i = 2; i <= n; i++) printf("%d ", dmin[i]);
return 0;
}