Pagini recente » Cod sursa (job #900698) | Cod sursa (job #878912) | Cod sursa (job #2805949) | Cod sursa (job #3135967) | Cod sursa (job #1824632)
#include <iostream>
#include <fstream>
using namespace std;
ifstream intrare("dijkstra.in");
ofstream iesire("dijkstra.out");
struct graf
{
int nod, dist;
graf *urm;
};
int n, m;
graf *a[50001];
const int inf=1<<30;
int dist[50001], viz[50001], poz[50001], k;
void adaugare(int i, int nod, int dist)
{
graf *q = new graf;
q->nod = nod;
q->dist = dist;
q->urm = a[i];
a[i] = q;
}
void citire()
{
intrare>>n>>m;
int x,y,z;
for(int i=1; i<=m; i++)
{
intrare>>x>>y>>z;
adaugare(x, y, z);
}
}
void schimbare(int i, int j)
{
int t = viz[i];
viz[i] = viz[j];
viz[j] = t;
}
void upheap(int nod)
{
int tata;
while ( nod > 1 )
{
tata = nod >> 1;
if ( dist[ viz[tata] ] > dist[ viz[nod] ] )
{
poz[ viz[nod] ] = tata;
poz[ viz[tata] ] = nod;
schimbare(tata, nod);
nod = tata;
}
else
nod = 1;
}
}
void downheap(int nod)
{
int f;
while ( nod <= k )
{
f = nod;
if ( (nod<<1) <= k )
{
f = nod << 1;
if ( f + 1 <= k )
if ( dist[ viz[f + 1] ] < dist[ viz[f] ] )
f++;
}
else
return;
if ( dist[ viz[nod] ] > dist[ viz[f] ] )
{
poz[ viz[nod] ] = f;
poz[ viz[f] ] = nod;
swap(nod, f);
nod = f;
}
else
return;
}
}
void dijkstra_heap()
{
for ( int i = 2; i <= n; i++ )
{
dist[i] = inf;
poz[i] = -1;
}
poz[1] = 1;
viz[++k] = 1;
while ( k )
{
int minn = viz[1];
schimbare(1, k);
poz[ viz[1] ] = 1;
--k;
downheap(1);
graf *q = a[minn];
while ( q )
{
if ( dist[q->nod] > dist[minn] + q->dist )
{
dist[q->nod] = dist[minn] + q->dist;
if ( poz[q->nod] != -1 )
upheap( poz[q->nod] );
else
{
viz[++k] = q->nod;
poz[ viz[k] ] = k;
upheap( k );
}
}
q = q->urm;
}
}
}
int main()
{
citire();
dijkstra_heap();
for(int i=2; i<=n; i++)
if(dist[i]==inf)
iesire<<0<<" ";
else
iesire<<dist[i]<<" ";
return 0;
}