Cod sursa(job #1370299)

Utilizator NacuCristianCristian Nacu NacuCristian Data 3 martie 2015 13:49:26
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#define inf 0x7fffffff
using namespace std;

int m,n,k;
int dmin[2010],nodk[2010],nrk[2010];


struct nod
{
    int x;
    int c;

    void atr(int a,int b)
    {
        x=a;
        c=b;
    }

    bool operator()(int a, int b)
    {

        if(nrk[a]!=nrk[b])
            return nrk[a]>nrk[b];
        else
            return dmin[a]>dmin[b];
    }
};

vector <nod> v[2010];
priority_queue<int, vector<int>, nod> q;

void citire()
{
    freopen("ubuntzei.in","r",stdin);
    scanf("%d %d\n%d",&n,&m,&k);
    for(int i=0;i<k;i++)
    {
        int a;
        scanf(" %d",&a);
        nodk[a]=1;
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        nod p,q;
        p.atr(a,c);
        q.atr(b,c);
        v[a].push_back(q);
        v[b].push_back(p);
    }
}

void dijkstra()
{
    q.push(1);
    for(int i=2;i<=m;i++)
        dmin[i]=inf;

    while(!q.empty())
    {
        int t=q.top();
        q.pop();
        for(int i=0;i<v[t].size();i++)
            if((nrk[v[t][i].x]<nrk[t]+nodk[v[t][i].x] && nrk[t]<=k) || (nrk[v[t][i].x]==nrk[t] && dmin[v[t][i].x]>dmin[t]+v[t][i].c))
            {

                nrk[v[t][i].x]=nrk[t]+nodk[v[t][i].x];
                nodk[v[t][i].x]=0;
                dmin[v[t][i].x]=dmin[t]+v[t][i].c;
                if(v[t][i].x!=n)
                    q.push(v[t][i].x);
            }
    }
    freopen("ubuntzei.out","w",stdout);
    printf("%d",dmin[n]);

}

int main()
{
    citire();
    dijkstra();
    return 0;
}