Cod sursa(job #2863780)

Utilizator PalffyLehelPalffy Lehel PalffyLehel Data 7 martie 2022 10:58:28
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>

using namespace std;

int main()
{
    fstream f("ubuntzei.in");
    ofstream g("ubuntzei.out");

    int csucsokSzama, elekSzama;
    f >> csucsokSzama >> elekSzama;

    int k;
    f >> k;

    int szomszedok[k + 1];
    for (int i = 1; i < k + 1; i++)
    {
        f >> szomszedok[i];
        szomszedok[i]--;
    }
    szomszedok[0] = 0;

    int x, y, z;
    list<pair <int, int> > csucsok[csucsokSzama];
    list<pair <int, int> > :: iterator it;
    for (int i = 0; i < elekSzama; i++)
    {
        f >> x >> y >> z;
        csucsok[x - 1].push_back(make_pair(z, y - 1));
        csucsok[y - 1].push_back(make_pair(z, x - 1));
    }

    priority_queue<pair <int, int>, vector<pair <int, int> >,greater<pair <int, int> > > sor;
    sor.push(make_pair(0, 0));

    int hossz[csucsokSzama];
    fill_n(hossz, csucsokSzama, INT_MAX);
    hossz[0] = 0;

    int elottem[csucsokSzama];
    fill_n(elottem, csucsokSzama, -1);

    pair <int, int> elem;
    int suly = 0;

    for (int i = 0; i < k + 1; i++)
    {
        sor.push(make_pair(0, szomszedok[i]));
        fill_n(hossz, csucsokSzama, INT_MAX);
        hossz[szomszedok[i]] = 0;

        while(!sor.empty())
        {
            elem = sor.top();
            sor.pop();

            for(it = csucsok[elem.second].begin(); it != csucsok[elem.second].end(); it++)
            {
                if (hossz[elem.second] + it->first < hossz[it->second])
                {
                    hossz[it->second] = hossz[elem.second] + it->first;
                    sor.push(*it);
                }
            }
        }

        if (i < k)
        {
            suly += hossz[szomszedok[i + 1]];
        }

        else
        {
            suly += hossz[csucsokSzama - 1];
        }
    }


    g << suly;

    return 0;
}