Cod sursa(job #2693664)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 6 ianuarie 2021 18:21:24
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct p {
    int nod;
    int cost;
    bool operator<(const p& P) const {
        return cost > P.cost;
    }
};

struct mc {
    int x;
    int y;
    int cost;
    bool operator<(const mc& MC) const {
        return cost < MC.cost;
    }
};

const int N = 2001;
const int INF = 1 << 30;

vector<p> gr_init[N];
vector<mc> muchii;
priority_queue<p> pq;
int d[N], loc[N], sef[N];
bool viz[N];


void dijkstra(vector<p> gr[N], int src, int n) {
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
        viz[i] = false;
    }
    d[src] = 0;
    pq.push({ src, 0 });

    while (!pq.empty()) {
        p crt = pq.top();
        pq.pop();
        viz[crt.nod] = true;

        for (auto vec : gr[crt.nod])
            if (!viz[vec.nod] && crt.cost + vec.cost < d[vec.nod]) {
                d[vec.nod] = crt.cost + vec.cost;
                pq.push({ vec.nod, d[vec.nod] });
            }
    }
}

int sefsuprem(int x) {
    if (sef[x] == x)
        return x;
    return sef[x] = sefsuprem(sef[x]);
}

int apm(int n) {
    for (int i = 1; i <= n; ++i)
        sef[i] = i;
    sort(muchii.begin(), muchii.end());

    int sef_x, sef_y, cost = 0;
    for (int i = 0; i < muchii.size(); ++i) {
        sef_x = sefsuprem(muchii[i].x);
        sef_y = sefsuprem(muchii[i].y);
        if (sef_x != sef_y) {
            sef[sef_x] = sef_y;
            cost += muchii[i].cost;
        }
    }

    return cost;
}

int main() {
    ifstream in("ubuntzei.in");
    ofstream out("ubuntzei.out");

    int n, m, k;
    in >> n >> m >> k;
    for (int i = 0; i < k; ++i)
        in >> loc[i];
    int x, y, cost;
    while (m--) {
        in >> x >> y >> cost;
        gr_init[x].push_back({ y, cost });
        gr_init[y].push_back({ x, cost });
    }

    for (int i = 0; i < k; ++i) {
        dijkstra(gr_init, loc[i], n);
        for (int j = 1; j <= n; ++j) {
            if (j == 1 || j == n || find(loc, loc + k, j) != loc + k)
                muchii.push_back({ loc[i], j, d[j] });
        }
    }
    
    //apm pe "muchii"
    out << apm(n);

    in.close();
    out.close();
    return 0;
}