Pagini recente » Cod sursa (job #707530) | Cod sursa (job #2839192) | Cod sursa (job #1255757) | Cod sursa (job #1909129) | Cod sursa (job #602972)
Cod sursa(job #602972)
// Heap
#include <iostream>
#include <vector>
using namespace std;
#define maxN 50005
#define PB push_back
#define MP make_pair
#define inf (1 << 30)
int N, M, dim;
int H[maxN];
vector < pair <int, int> > lista[maxN];
bool cont[maxN];
int cost[maxN], poz[maxN];
void push (int nod)
{
if (nod == 1) return;
if ( cost[ H[nod / 2] ] <= cost[ H[nod] ] ) return;
swap (H[nod], H[nod / 2]);
swap (poz[H[nod]], poz[H[nod / 2]]);
push (nod / 2);
}
void pop (int nod)
{
int nodmin = nod, st = 2 * nod, dr = 2 * nod + 1;
if (st <= dim && cost[H[st]] < cost[H[nodmin]]) nodmin = st;
if (dr <= dim && cost[H[dr]] < cost[H[nodmin]]) nodmin = dr;
if (nodmin == nod) return;
swap (H[nod], H[nodmin]);
swap (poz[H[nod]], poz[H[nodmin]]);
pop (nodmin);
}
int main()
{
freopen ("dijkstra.in", "r", stdin);
freopen ("dijkstra.out", "w", stdout);
scanf ("%d %d", &N, &M);
while (M --)
{
int a, b, c;
scanf ("%d %d %d", &a, &b, &c);
lista[a]. PB ( MP (b, c) );
}
H[++ dim] = 1;
poz[1] = 1;
for (int i = 2; i <= N; ++ i)
{
cost[i] = inf;
H[++ dim] = i;
poz[i] = dim;
}
for (int i = 1; i <= N; ++ i)
{
int nod = H[1];
cont[nod] = true;
swap (H[1], H[dim]);
swap (poz[H[1]], poz[H[dim]]);
-- dim;
pop (1);
for (unsigned int t = 0; t < lista[nod].size(); ++ t)
{
int node = lista[nod][t].first;
if (cont[node]) continue;
if (cost[node] > cost[nod] + lista[nod][t].second)
{
cost[node] = cost[nod] + lista[nod][t].second;
int poz_h = poz[node];
if (poz_h / 2 >= 1 && cost[H[poz_h]] >= cost[H[poz_h / 2]]) pop (poz_h);
else push (poz_h);
}
}
}
for (int i = 2; i <= N; ++ i)
if (cost[i] != inf) printf ("%d ", cost[i]);
else printf ("0 ");
return 0;
}