Cod sursa(job #3251943)

Utilizator IleaIlea Bogdan Ilea Data 27 octombrie 2024 20:32:04
Problema Ubuntzei Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

string file="ubuntzei";
ifstream fin(file+".in");
ofstream fout(file+".out");

#define inf 10000001
#define endl '\n'

int n;
vector<long long> dist;
unordered_set<int> priet;
map<int, map<int, int> > g;
void dijkstra(int i)
{
    set<pair<long long, int>> s;
    s.insert({0, i});
    fill(dist.begin(), dist.end(), inf);
    dist[i]=0;
    while (!s.empty()){
        i=s.begin()->second;
        s.erase(s.begin());
        for (auto it:g[i]){
            if (dist[it.first]>dist[i]+(long long)(it.second)){
                s.erase({dist[it.first], it.first});
                dist[it.first]=dist[i]+(long long)(it.second);
                s.insert({dist[it.first], it.first});
            }
        }
    }
}
int main()
{
    int m, k;
    fin>>n>>m>>k;
    dist.resize(n+1);
    for (int i=0; i<k; i++){
        int x;
        fin>>x;
        priet.insert(x);
    }
    while (m){
        m--;
        int x, y, z;
        fin>>x>>y>>z;
        g[x][y]=z;
        g[y][x]=z;
    }
    dijkstra(1);
    //system("PAUSE");
    long long s=0;
    while (!priet.empty()){
        int minim=0;
        for (auto it:priet){
            //cout<<it<<" "<<dist[it]<<endl;
            if (dist[minim]>dist[it])minim=it;
        }
        s+=dist[minim];
        priet.erase(minim);
        dijkstra(minim);
    }
    fout<<s+dist[n];
    return 0;
}