Cod sursa(job #2864547)

Utilizator MokaDomos Mozes Moka Data 7 martie 2022 22:41:42
Problema Ubuntzei Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 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];
onmaga aktualis;
onmaga on;
void dijsktra(int kezd,int veg)
{
    int belson=veg;
    on.szam=kezd;
    on.osszeg=0;
    pq.push(on);
    tav[kezd]=0;
    bool megvan=true;
    for (int i=0; i<=2000; i++)
    {
        tav[i]=184467440737095516;
    }
    for (int i=0; i<=2000; i++)
    {
        jart[i]=false;
    }
    //bool megvan=true;
    while (!pq.empty())
    {
        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])
            {
                unsigned long long 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);
                    }
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>kdb;
    kotelezovarosok.push_back(1);
    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);
    }
    for (int i=0; i<kotelezovarosok.size(); i++)
    {
        dijsktra(kotelezovarosok[i],kotelezovarosok[i+1]);
    }
    cout<<minm;
    return 0;
}