Cod sursa(job #2145283)

Utilizator edynator34Nechitoaia George-Edward edynator34 Data 27 februarie 2018 11:28:06
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#define nm 10005
#define inf (1<<30)
using namespace std;
ifstream in("ubuntzei.in");
ofstream out("ubuntzei.out");
vector < pair < int , int > > graf[nm];
int s[nm],d[nm],i,n,m,k,oras[nm],x,y,c,distanta;
bitset <nm> vizitat;
struct comp{
    bool operator()(int x, int y){
        return d[x]>d[y];
                                    }
};
priority_queue <int, vector < int > , comp > q;
void dij(int sursa){
    for(i=1;i<=n;++i){
        d[i]=inf;
    }
    d[sursa]=0;
    vizitat[sursa]=true;
    q.push(sursa);
    vector  < pair < int , int > > ::iterator it;
    while(!q.empty()){
        int nodcurent=q.top();
        q.pop();
        vizitat[nodcurent]=false;
        for(it=graf[nodcurent].begin();it!=graf[nodcurent].end();++it){
            int vecin=it->first;
            int cost =it->second;
            if(d[vecin]>d[nodcurent]+cost){
                d[vecin]=d[nodcurent]+cost;
                if(!vizitat[vecin]){
                    vizitat[vecin]=true;
                    q.push(vecin);
                }
            }
        }

    }



}
void afiseaza ()
{
    int i;
    for (i=1;i<=n;i++)
        if (d[i]!=inf)
            out<<d[i]<<" ";
        else out<<"0 ";
    out<<"\n";
}

int main()
{
    in>>n>>m>>k;
    for(int i=1;i<=k;++i) in>>oras[i];
    sort(oras+1,oras+k+1);
    for(int i=1;i<=m;++i){
        in>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
        graf[y].push_back(make_pair(x,c));
                         }

       if(k==0){
        dij(1);
        out<<d[n];
        return 0;
       }
       distanta=0;
       dij(oras[1]);
       distanta+=d[1];
       for(int omom=2;omom<=k;++omom){
       dij(oras[omom]);
       distanta+=d[oras[omom-1]];
       }
       distanta+=d[n];
       out<<distanta<<' ';


    return 0;
}