Cod sursa(job #2864524)

Utilizator MokaDomos Mozes Moka Data 7 martie 2022 22:20:26
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <list>
#include <fstream>
#include <queue>
#include <vector>
struct szomszed
{
    int vegpont;
    int suly;
};
struct onmaga
{
    int szam;
    unsigned long long osszeg=0;
};
struct CompareSuly
{
    bool operator()(onmaga &p1, onmaga &p2)
    {
        return p1.osszeg > p2.osszeg;
    }
};
using namespace std;
ifstream cin("ubuntzei.in");
ofstream cout("ubuntzei.out");
int m,n,kdb;
list<szomszed> v[2001];
vector<int> kotelezovarosok;
bool k[2001];
priority_queue<onmaga,vector<onmaga>,CompareSuly> pq;
unsigned long long minm=0;
bool jart[2001];
unsigned long long tav[2001];
int main()
{
    cin>>n>>m>>kdb;
    for (int i=0; i<kdb; i++)
    {
        int a;
        cin>>a;
        kotelezovarosok.push_back((a));
    }
    kotelezovarosok.push_back(n);
    for (int i=0; i<m; i++)
    {
        int a;
        int b;
        int c;
        cin>>a>>b>>c;
        szomszed l;
        l.vegpont=b;
        l.suly=c;
        v[a].push_back(l);
        l.vegpont=a;
        v[b].push_back(l);
    }
    onmaga aktualis;
    onmaga on;
    int elozo=1;
    int belson;
    for (int i: kotelezovarosok)
    {
            while(!pq.empty())
            {
                pq.pop();
            }
            for (int i=1; i<=n; i++)
            {
                tav[i]=184467440737095516;
            }
            for (int i=0;i<=n;i++){
                jart[i]=false;
            }
            on.szam=elozo;
            on.osszeg=0;
            pq.push(on);
            tav[elozo]=0;
            belson=i;
            bool megvan=true;
            while (!pq.empty() && megvan)
            {
                aktualis = pq.top();
                if(aktualis.szam==belson)
                {
                    minm+=aktualis.osszeg;
                    //cout<<aktualis.osszeg<<endl;
                    megvan=false;
                }
                pq.pop();
                if(megvan){
                jart[aktualis.szam]=true;
                for (szomszed l : v[aktualis.szam])
                {
                    int tavolsag=aktualis.osszeg+l.suly;
                    if(jart[l.vegpont]!=true)
                    {
                        if(tav[l.vegpont]>tavolsag)
                        {
                            tav[l.vegpont]=tavolsag;
                            onmaga ledik;
                            ledik.szam=l.vegpont;
                            ledik.osszeg=tav[l.vegpont];
                            pq.push(ledik);
                        }
                    }
                }
            }
            }
            elozo=i;
    }
    cout<<minm;
    return 0;
}