Cod sursa(job #2494622)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 18 noiembrie 2019 10:30:16
Problema Ubuntzei Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
#define MOD 1999999973
#define ull unsigned long long
#define inf 2000001

using namespace std;

ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");

vector<pair<int,int>> G[50005];
priority_queue<pair<int,int>> Q;
int val[5005];
int viz[5005];
int eloc[5005];
int loc[100];
int n,m,k,sumsol;

int findmin(){
    int sol;
    while(viz[Q.top().second] == 1){
        Q.pop();
    }
    sol = Q.top().second;
    Q.pop();
    return sol;
}

void Dijkstra(int a){
    int i,j,vecin,cost,minim;
    while(!Q.empty()){
        Q.pop();
    }
    for(i = 1; i <= n; ++i){
        viz[i] = 0;
    }
    for(i = 1; i <= n; ++i){
        if(i != a){
            val[i] = inf;
        }else{
            val[i] = 0;
        }
        Q.push(make_pair(-val[i],i));
    }
    for(i = 1; i <= n; ++i){
        minim = findmin();
        viz[minim] = 1;
        for(j = 0; j < G[minim].size(); j++){
            vecin = G[minim][j].first;
            cost = G[minim][j].second;
            if(val[vecin] > val[minim] + cost){
                val[vecin] = val[minim] + cost;
                Q.push(make_pair(-val[vecin],vecin));
            }
        }
    }
}

int main()
{
    int i,j,a1,a2,c1,nrloc,urm,minim;
    fin>>n>>m>>k;
    nrloc = k;
    for(i = 1; i <= k; ++i){
        fin>>loc[i];
        eloc[loc[i]] = 1;
    }
    for(i = 1; i <= m; ++i){
        fin>>a1>>a2>>c1;
        G[a1].push_back(make_pair(a2,c1));
        G[a2].push_back(make_pair(a1,c1));
    }
    Dijkstra(1);
    while(nrloc--){
        minim = inf;
        for(i = 1; i <= n; i++){
            if(eloc[i]){
                if(minim > val[i]){
                    minim = val[i];
                    urm = i;
                }
            }
        }
        eloc[urm] = 0;
        sumsol += minim;
        Dijkstra(urm);
    }
    sumsol += val[n];
    fout<<sumsol<<endl;
    return 0;
}