Cod sursa(job #1075123)

Utilizator ThomasFMI Suditu Thomas Thomas Data 8 ianuarie 2014 17:23:33
Problema Ubuntzei Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define Nmax 2001

ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

int n,m,i,a,b,c,k,kv[Nmax],sum;
vector<int> v[Nmax],w[Nmax];

struct muchie{int t,a,b;};

class Compare {
public:
    bool operator()(muchie& t1, muchie& t2)
    {
       if (t1.t > t2.t) return true;
       return false;
    }
};

priority_queue<muchie, vector<muchie>, Compare> cd;

int djk(int s)
{
    muchie u;
    int i,e;
    int viz[Nmax],dr[Nmax];
    for(i=1;i<=n;i++) viz[i]=dr[i]=0;

    e=v[s].size();
    for(i=0;i<e;i++) if(viz[v[s].at(i)]==0)
    {
        u.a=s;
        u.b=v[s].at(i);
        u.t=w[s].at(i)+dr[s];
        cd.push(u);
    }

    viz[s]=1;

    while(!cd.empty())
    {
        if(kv[s]==0)
        {
            //g<<cd.top().a<<","<<cd.top().b<<" -> "<<cd.top().t<<"\n";
            s=cd.top().b;
            if(viz[s]==0)
            {
                dr[s]=cd.top().t;
                cd.pop();

                e=v[s].size();
                for(i=0;i<e;i++) if(viz[v[s].at(i)]==0)
                {
                    u.a=s;
                    u.b=v[s].at(i);
                    u.t=w[s].at(i)+dr[s];
                    cd.push(u);
                }
            }
            else cd.pop();
            viz[s]=1;
        }
        else cd.pop();
    }

    if(k==0) sum+=dr[n];
    else sum+=dr[s];
    k--;
    kv[s]=0;

    //for(i=1;i<=n;i++) g<<dr[i]<<" ";g<<"\n";
    //if(k!=-1) g<<s<<" = "<<dr[s]<<"\n";
    //else g<<n<<" = "<<dr[n]<<"\n";

    return s;
}

int main()
{
    f>>n>>m;

    f>>k;
    for(i=1;i<=k;i++)
    {
        f>>a;
        kv[a]=1;
    }

    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        w[a].push_back(c);
        v[b].push_back(a);
        w[b].push_back(c);
    }

    int q=1;
    while(k>0)
    {
        //g<<q<<" -> ";
        q=djk(q);
    }
    //g<<q<<" -> ";
    djk(q);

    g<<sum<<"\n";

    f.close();
    g.close();
    return 0;
}