Cod sursa(job #2100462)

Utilizator pibogaBogdan piboga Data 5 ianuarie 2018 17:47:40
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <climits>

#define pb push_back
#define mkp make_pair

using namespace std;

const int NNOD=36020;
const int INF=9999999;

vector < pair<int, int> > lst[NNOD];
vector  <pair<int, int> >::iterator it;
set < pair<int,int> > snot;

int nnod,nmuc,x,y,cost,ifort,nodcrt,add,veccrt,dnew,nfort;
int inod,lgmuc,imuc;
int vdist[NNOD],zfort[NNOD],vfort[NNOD],aux;
bool viz[NNOD];


int main()
{
    freopen ("catun.in","r",stdin);
    freopen ("catun.out","w",stdout);

    scanf ("%d%d%d",&nnod,&nmuc,&nfort);

    for (inod=1; inod<=nnod; ++inod)
    {
        vdist[inod]=INF;
    }

    for (ifort=1; ifort<=nfort; ++ifort)
    {
        scanf("%d",&x);
        vdist[x]=0;
        vfort[ifort]=x;
        zfort[x]=x;
        snot.insert(mkp(0,x));

    }


    for (imuc=1; imuc<=nmuc; ++imuc)
    {
        scanf ("%d%d%d",&x,&y,&cost);
        lst[x].pb(mkp(cost,y));
        lst[y].pb(mkp(cost,x));
    }


    while (!snot.empty())
    {
        nodcrt=snot.begin()->second;
        snot.erase(snot.begin());

        //if (viz[nodcrt]) continue;
       // viz[nodcrt]=1;

        for (it=lst[nodcrt].begin(); it!=lst[nodcrt].end(); ++it)
        {
            lgmuc=it->first;
            veccrt=it->second;

            dnew=vdist[nodcrt]+lgmuc;

            if (dnew<vdist[veccrt])
            {
                if (vdist[veccrt]!=INF)
                {
                    snot.erase(snot.find(mkp(vdist[veccrt],veccrt)));
                }
                zfort[veccrt]=zfort[nodcrt];
                vdist[veccrt]=dnew;
                snot.insert(mkp(dnew,veccrt));

            }

            if (vdist[veccrt]==dnew)
            {
                aux=zfort[veccrt];
                zfort[veccrt]=min(aux,zfort[nodcrt]);
            }
        }

    }

    for (ifort=1; ifort<=nfort; ++ifort)
    {
        zfort[vfort[ifort]]=0;
    }

    for (inod=1; inod<=nnod; ++inod)
    {
        printf("%d ",zfort[inod]);
    }





    return 0;
}