Cod sursa(job #1856633)

Utilizator ioan_cernovshi00Cernovschi Ioan ioan_cernovshi00 Data 25 ianuarie 2017 10:36:51
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.62 kb
#include <cstdio>
using namespace std;

FILE *in = fopen("dijkstra.in","r");
FILE *out = fopen("dijkstra.out","w");

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()
{
    fscanf(in, "%d %d", &n, &m);
    int x,y,z;
    for(int i=1; i<=m; i++)
    {
        fscanf(in, "%d %d %d", &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;

            schimbare(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)
            fprintf(out, "0 ");
        else
            fprintf(out, "%d ", dist[i]);
    return 0;
}