Cod sursa(job #2534599)

Utilizator XXMihaiXX969Gherghinescu Mihai Andrei XXMihaiXX969 Data 30 ianuarie 2020 19:34:14
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <bits/stdc++.h>

using namespace std;

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

#define int long long

const int DIM = 2e3 + 5;
const int oo = 1e9;

int n, m, k;

bool ex[DIM];
int d[DIM];
int loc[DIM];


vector < pair <int, int> > l[DIM];

set <int> s;

struct cp
{
   bool operator() (int x, int y)
   {
       return d[x] > d[y];
   }
};


priority_queue <int,vector < int >, cp > c;

vector <pair <int,int> > l2[DIM];


void dijktra(int x)
{


   for(int i = 1; i <= n; i++)
    {
     ex[i] = false;
     d[i] = oo;
    }

    ex[x] = true;
    d[x] = 0;
    c.push(x);

    while(!c.empty())
    {
        int nod = c.top();

        c.pop();
        ex[nod] = false;

        for(int i = 0; i < l[nod].size(); i++)
        {
            int vec = l[nod][i].first;
            int cost = l[nod][i].second;

            if(d[nod] + cost < d[vec])
            {
                d[vec] = d[nod] + cost;

                if(ex[vec] == false)
                {
                    ex[vec] = true;
                    c.push(vec);
                }
            }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(d[i] != oo)
        if(s.find(i)!= s.end())
        {
            l2[x].push_back(make_pair(i,d[i]));
        }

    }

}

priority_queue <pair <int, pair <int,int> > > c2;

bool viz[DIM];

void prim()
{
    int rez = 0;

    for(int i = 0; i < l2[1].size(); i++)
    {
        int nod = l2[1][i].first;
        int cost = l2[1][i].second;
        c2.push(make_pair(-cost,make_pair(1,nod)));
    }

    viz[1] = true;

    int nr = 1;
    while(nr < k && !c2.empty())
    {

        while(viz[c2.top().second.second])
        c2.pop();

        int nod = c2.top().second.second;
        int cy = c2.top().first;

        rez += cy;
        nr++;
        c2.pop();
        viz[nod] = true;

        for(int i = 0; i < l2[nod].size(); i++)
        {
            int vec = l2[nod][i].first;
            int cost = l2[nod][i].second;

            if(viz[vec] == false)
                c2.push(make_pair(-cost,make_pair(nod,vec)));
        }
    }

    out << -rez;
}

 main()
{

    in >> n >> m;

    in >> k;

    for(int i = 1; i <= k; i++)
      {
          in >> loc[i];

          s.insert(loc[i]);
      }

    if(s.find(1) == s.end())
    {s.insert(1);
     k++;
     loc[k] = 1;
    }
    if(s.find(n) == s.end())
    {s.insert(n);
     k++;
     loc[k] = n;
    }



    for(int i = 1; i <= m; i++)
    {
        int x, y, z;

        in >> x >> y >> z;

        l[x].push_back(make_pair(y,z));
        l[y].push_back(make_pair(x,z));
    }




    for(int i = 1; i <= k; i++)
    {
        dijktra(loc[i]);
    }

    prim();

    return 0;
}