This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, m;
cin >> n >> m;
const int maxm = 1e6, maxn = 700;
struct edge {
int a, b, we;
};
vector<edge> elist(maxm);
for (int i = 0; i < m; i++)
cin >> elist[i].a >> elist[i].b >> elist[i].we;
int qs;
cin >> qs;
while (qs--) {
vector<int> dsu(maxn);
iota(dsu.begin(), dsu.end(), 0);
int x;
cin >> x;
vector<edge> ve(elist);
for (int i = 0; i < m; i++) {
ve[i].we = abs(ve[i].we - x);
}
sort(ve.begin(), ve.end(), [&](edge a, edge b) { return a.we < b.we; });
function<int(int)> par = [&](int cur) {
if (dsu[cur] == cur)
return cur;
dsu[cur] = par(dsu[cur]);
return dsu[cur];
};
int cost = 0;
for (auto a : ve) {
if (par(a.a) != par(a.b)) {
cost += a.we;
dsu[par(a.a)] = par(a.b);
}
}
cout << cost << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |