Pagini recente » Cod sursa (job #2009638) | Cod sursa (job #1661124) | Cod sursa (job #2742852) | Cod sursa (job #938431) | Cod sursa (job #2693664)
#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;
}