Pagini recente » Cod sursa (job #2492245) | Cod sursa (job #3242929) | Cod sursa (job #2957802) | Cod sursa (job #1160102) | Cod sursa (job #184381)
Cod sursa(job #184381)
#include<stdio.h>
#define INPUT "dijkstra.in"
#define OUTPUT "dijkstra.out"
#define NMAX 50002
#define INFI 2000000000
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
typedef struct Graph
{
long node;
long cost;
Graph *next;
};
Graph *List[ NMAX ];
long N, M, Nmax;
long heap[ NMAX ], nodHeap[ NMAX ], poz[ NMAX ], Minim[ NMAX ], util[ NMAX ];
void readValues()
{
long X, Y, Z;
Graph *adr;
fscanf(fin, "%ld %ld", &N, &M);
for(long i = 0; i < M; ++i)
{
fscanf(fin, "%ld %ld %ld", &X, &Y, &Z);
adr = new Graph;
adr -> node = Y;
adr -> cost = Z;
adr -> next = List[ X ];
List[ X ] = adr;
}
}
void swap(long &V1, long &V2)
{
V1 = V1 + V2;
V2 = V1 - V2;
V1 = V1 - V2;
}
void upHeap(long p)
{
while( p > 0 )
{
if( heap[ p / 2 ] > heap[ p ] )
{
swap( heap[ p / 2 ], heap[ p ] );
swap( nodHeap[ p / 2 ], nodHeap[ p ] );
swap( poz[ nodHeap[ p / 2 ] ], poz[ nodHeap[ p ] ] );
p /= 2;
}
else
return;
}
}
void downHeap(long p)
{
long P;
while( p <= Nmax)
{
if( 2 * p <= Nmax)
{
P = 2 * p;
if( 2 * p + 1 <= Nmax)
if(heap[ 2 * p ] > heap[ 2 * p + 1 ])
P = 2 * p + 1;
if( heap[ P ] < heap[ p ])
{
swap( heap[ P ], heap[ p ] );
swap( nodHeap[ P ], nodHeap[ p ] );
swap( poz[ nodHeap[ P ] ], poz[ nodHeap[ p ] ] );
p = P;
}
else return;
}
else return;
}
}
void solveFunction()
{
Graph *adr;
long cur;
for(long i = 1; i <= N; ++i)
{
heap[ i ] = -1;
poz[ i ] = -1;
nodHeap[ i ] = -1;
}
Nmax = 1;
heap[ Nmax ] = 0;
nodHeap[ Nmax ] = 1;
poz[ 1 ] = Nmax;
while( Nmax > 0)
{
cur = nodHeap[ 1 ];
Minim[ cur ] = heap[ 1 ];
poz[ nodHeap[ 1 ] ] = -1;
heap[ 1 ] = heap[ Nmax ];
nodHeap[ 1 ] = nodHeap[ Nmax ];
poz[ nodHeap[ 1 ] ] = 1;
--Nmax;
adr = List[ cur ];
while(adr != NULL)
{
if(poz[ adr -> node ] == -1)
{
++Nmax;
heap[ Nmax ] = Minim[ cur ] + adr -> cost;
nodHeap[ Nmax ] = adr -> node;
poz[ nodHeap[ Nmax ] ] = Nmax;
upHeap( Nmax );
}
else
if(poz[ adr -> node ] != -1)
if(heap[ poz[ adr -> node ] ] > Minim[ cur ] + adr -> cost)
{
heap[ poz[ adr -> node ] ] = Minim[ cur ] + adr -> cost;
upHeap( poz[ adr -> node ] );
}
adr = adr -> next;
}
}
for(long i = 1; i < N; ++i)
fprintf(fout, "%ld ", Minim[ i + 1 ]);
fprintf(fout, "\n");
}
int main()
{
readValues();
solveFunction();
fclose(fin);
fclose(fout);
return 0;
}