Cod sursa(job #891960)

Utilizator marius_devMarius Filiuta marius_dev Data 25 februarie 2013 21:24:38
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
//#include<iostream>
#include<fstream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<string.h>

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<edge> graph_mc[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");

    int n,m,k,c[MAX_SIZE],viz[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+1;i++)
        viz[i]=0;
    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));
            }
        }
        int min=i+1;
        viz[min]=1;
        for(int j=1;j<=k;j++)
        {
            if(!viz[j])
                if(dist[c[j]]<dist[c[min]])
                    min=j;
            graph_mc[i].pb(mp(dist[c[j]],j));
            graph_mc[j].pb(mp(dist[c[j]],i));
        }
        i=min-1;
        drum+=dist[c[min]];
        dist.clear();
        dist.assign(MAX_SIZE,oo);
    }

    //viz[k+1]=1;
    out<<drum;
    in.close();
    out.close();

    return 0;

}