Cod sursa(job #2864065)

Utilizator david.kerekesKerekes David david.kerekes Data 7 martie 2022 15:52:12
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> utHossz;

int n,m,k;
bool vanBaratAvarosban[2001]={false};
vector<utHossz> terkep[2001];
int d[2001];
bool elemeAzOptSornak[2001]={false};

struct osszehasonlitas{
    bool operator()(int x,int y)
    {
        return d[x]>d[y];
    }
};

priority_queue<int, vector<int>,osszehasonlitas> optimalizalandoElemek;

void beolvas()
{
    ifstream fin("ubuntzei.in");
    fin>>n>>m>>k;
    int a,b,c;
    for(int i=1;i<=k;i++)
    {
        fin>>a;
        vanBaratAvarosban[a]=true;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        terkep[a].push_back(make_pair(b,c));
        terkep[b].push_back(make_pair(a,c));
    }
    fin.close();
}

void dijkstra(int kezdoCsucs)
{
    for(int i=1;i<=n;i++)
    {
        d[i]=99999;
    }
    d[kezdoCsucs]=0;
    optimalizalandoElemek.push(kezdoCsucs);
    elemeAzOptSornak[kezdoCsucs]=true;
    while(!optimalizalandoElemek.empty())
    {
        int csucs=optimalizalandoElemek.top();
        optimalizalandoElemek.pop();
        elemeAzOptSornak[csucs]=false;
        for(size_t i=0;i<terkep[csucs].size();i++)
        {
            int szomszed=terkep[csucs][i].first;
            int tavolsag=terkep[csucs][i].second;
            if(d[csucs]+tavolsag<d[szomszed])
            {
                d[szomszed]=d[csucs]+tavolsag;
                if(!elemeAzOptSornak[szomszed])
                {
                    optimalizalandoElemek.push(szomszed);
                    elemeAzOptSornak[szomszed]=1;
                }
            }
        }
    }
}


int main() {
    int l=0;
    beolvas();
    dijkstra(1);
    int mini,miniIn=1;
    while(k!=0)
    {
        mini=999999;
        for(int i=1;i<=n;i++)
        {
            if(vanBaratAvarosban[i]&&d[i]<mini)
            {
                mini=d[i];
                miniIn=i;
            }
        }
        if(mini!=999999) {
            l += mini;
            vanBaratAvarosban[miniIn] = false;
        }
        else
        {
            break;
        }

    }
    dijkstra(miniIn);
    l+=d[n];
    ofstream fout("ubuntzei.out");
    fout<<l;
    fout.close();
    return 0;
}