Cod sursa(job #890702)

Utilizator marius_devMarius Filiuta marius_dev Data 25 februarie 2013 11:24:51
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<fstream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>

using namespace std;

#define edge pair<int,int>
#define mp make_pair
#define pb push_back
#define node second
#define cost first

const int MAX_SIZE=2e3+3;
const int oo=(1<<30)-1;

vector<edge> graph[MAX_SIZE];
vector<int> dist(MAX_SIZE,oo);
vector<edge>::iterator it,end;

priority_queue<edge, vector<edge>, greater<edge> > heap;

int main ()
{
    ifstream in("ubuntzei.in");
    ofstream out("ubuntzei.out");

    long long n,m,k,c[MAX_SIZE],drum=0;
    in>>n>>m>>k;
    c[0]=1;
    c[k+1]=n;
    for(int i=1;i<=k;i++)
        in>>c[i];
    sort(c,c+k+1);
    for(int i=1;i<=m;i++)
    {
        int cTo,cFrom,cCost;
        in>>cFrom>>cTo>>cCost;
        graph[cFrom].pb(mp(cCost,cTo));
        //graph[cTo].pb(mp(cCost,cFrom));
    }
    for(int i=0;i<=k;i++)
    {
        if(c[i]==c[i+1])
            continue;
        heap.push(mp(0,c[i]));
        dist[c[i]]=0;
        while(!heap.empty())
        {
            int current=heap.top().node;
            heap.pop();
            it=graph[current].begin();
            end=graph[current].end();
            for(;it!=end;++it)
            if(dist[current]+it->cost<dist[it->node])
            {
                dist[it->node]=dist[current]+it->cost;
                heap.push(mp(dist[it->node],it->node));
            }
        }
        drum+=dist[c[i+1]];
        dist.clear();
    }
    out<<drum;
    in.close();
    out.close();

    return 0;

}