Cod sursa(job #2858982)

Utilizator Florinos123Gaina Florin Florinos123 Data 28 februarie 2022 18:18:25
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f ("ubuntzei.in");
ofstream g ("ubuntzei.out");

int n, m, lg;

bool v[2005];

int a[2005][2005];

int tata[2005];

bool u[2005];

const int inf = 2e9;

int nr_muchii;

struct muchie {
 int x, y, cost;
}muchii[10005];

bool cmp (muchie a, muchie b)
{
    if (a.cost <= b.cost)
        return true;
    return false;
}

int Radacina (int nod)
{
    if (tata[nod] == 0)
        return nod;

    int k = Radacina(tata[nod]);
    tata[nod] = k;
    return k;
}

void Uneste (int x, int y)
{
    int rx = Radacina(x); int ry = Radacina(y);

    tata[ry] = rx;
}

int main()
{
    f >> n >> m >> lg;
    for (int i=1; i<=lg; i++)
    {
        int x; f >> x;
        v[x] = 1;
    }

    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            a[i][j] = inf;

    for (int i=1; i<=n; i++)
        tata[i] = 0;

     while (m --)
     {
         int i, j, c;
         f >> i >> j >> c;
         a[i][j] = a[j][i] = c;
     }

     for (int k=1; k<=n; k++)
     {
         for (int i=1; i<=n; i++)
         {
             for (int j=1; j<=n; j++)
             {
                 if (i != j && a[i][k] != inf && a[j][k] != inf)
                    if (a[i][k] + a[k][j] < a[i][j])
                       a[i][j] = a[i][k] + a[k][j];
             }
         }
     }

     v[1] = 1; v[n] = 1;

     int bound = 0;
     for (int i=1; i<=n; i++)
        if (v[i]) bound ++;

     for (int i=1; i<=n; i++)
     {
         if (v[i] == 1)
         {
             for (int j=1; j<=n; j++)
             {
                 if (v[j] && i != j)
                 {
                     nr_muchii ++;
                     muchii[nr_muchii] = {i, j, a[i][j]};
                 }
             }
         }
     }

     sort(muchii+1, muchii+nr_muchii+1, cmp);

     int sum = 0;
     int nrMuchii = 0;

     for (int i=1; i<=nr_muchii; i++)
     {
         int x = muchii[i].x;
         int y = muchii[i].y;
         int cost = muchii[i].cost;

         if (Radacina(x) != Radacina(y))
         {
             Uneste(x, y);
             sum += cost;
             nrMuchii ++;
         }

         if (nrMuchii == bound-1) break;
     }

     g << sum;


    return 0;
}