Cod sursa(job #890678)

Utilizator marius_devMarius Filiuta marius_dev Data 25 februarie 2013 11:15:17
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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");

    unsigned 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++)
    {
        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;

}