Cod sursa(job #2863935)

Utilizator PalffyLehelPalffy Lehel PalffyLehel Data 7 martie 2022 13:54:49
Problema Ubuntzei Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>

using namespace std;

int a = 2147483647;

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

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

    int k;
    f >> k;

    int b;
    int szomszedok[k];
    bool latogatando[csucsokSzama];
    bool latogatott[k];
    fill_n(latogatando, csucsokSzama, false);
    fill_n(latogatott, k, false);
    for (int i = 0; i < k ; i++)
    {
        f >> b;
        szomszedok[i] = b - 1;
        latogatando[b - 1] = true;
    }

    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];

    pair <int, int> elem;

    int start = 0, mini, index, suly = 0;
    for (int i = 0; i < k; i++)
    {
        mini = a;
        index = -1;
        sor.push(make_pair(0, start));
        fill_n(hossz, csucsokSzama, a);
        hossz[start] = 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);
                }
            }
        }

        for (int j = 0; j < csucsokSzama; j++)
        {
            if (latogatando[j] && !latogatott[j] && mini > hossz[j])
            {
                latogatott[j] = true;
                mini = hossz[j];
                index = j;
            }
        }

        suly += mini;
        start = index;
    }

    fill_n(hossz, csucsokSzama, a);
    hossz[start] = 0;
    sor.push(make_pair(0, start));
    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);
            }
        }
    }

    suly += hossz[csucsokSzama - 1];

    g << suly;

    return 0;
}