Cod sursa(job #1654848)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 17 martie 2016 15:57:29
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <stdlib.h>
#include <set>
#define mp make_pair
#define pb push_back
#define INF 1000000000

using namespace std;

ifstream fin("catun.in");
ofstream fout("catun.out");

struct lista{int val, cost;};

int n, m, f, i, F[36005], x, y, c, d[36005], minim, ord;
lista *A[36005];

set < pair <int, int> > heap; // val si idx

void DJ(int x)
{
    int val, id, i;
    lista p;
    for (i=1; i<=n; i++)
        d[i]=INF;
    d[x]=0;
    heap.insert(mp(0, x));
    while (heap.size() > 0)
    {
        val = (*heap.begin()).first;
        id = (*heap.begin()).second;
        heap.erase(*heap.begin());
        for (i=1; i<=A[id][0].val; i++)
        {
            p=A[id][i];
            if (d[p.val] > p.cost + val)
            {
                d[p.val]=p.cost+val;
                heap.insert(mp(d[p.val], p.val));
            }
        }
    }
}

int main()
{
    int j;
    fin>>n>>m>>f;
    for (i=1; i<=f; i++)
    {
        fin>>x;
        F[x]=1;
    }
    for (i=1; i<=n; i++)
    {
        A[i] = (lista *) realloc(A[i], 2*sizeof(int));
        A[i][0].val=0;
    }
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        A[x][0].val++;
        A[x] = (lista *) realloc(A[x], (A[x][0].val+1)*2*sizeof(int));
        A[x][A[x][0].val].val=y;
        A[x][A[x][0].val].cost=c;
        A[y][0].val++;
        A[y] = (lista *) realloc(A[y], (A[y][0].val+1)*2*sizeof(int));
        A[y][A[y][0].val].val=x;
        A[y][A[y][0].val].cost=c;
    }
    for (i=1; i<=n; i++)
    {
        if (F[i]==0)
        {
            DJ(i);
            minim=INF;
            ord=0;
            for (j=1; j<=n; j++)
            {
                if (F[j]==1 && d[j]<minim)
                {
                    minim=d[j];
                    ord=j;
                }
            }
            if (minim==INF)
                fout<<0<<" ";
            else
                fout<<ord<<" ";
        }
        else
            fout<<0<<" ";
    }
    return 0;
}