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>
#define int long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
vector<int> dsu, sz;
int f(int x) { return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
void un(int a, int b)
{
a = f(a), b = f(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
dsu[b] = a, sz[a] += sz[b];
}
void solve()
{
int n, m;
cin >> n >> m;
vector<array<int, 3>> e0(m);
for (auto &i : e0)
cin >> i[1] >> i[2] >> i[0], --i[1], --i[2];
int q;
cin >> q;
while (q--)
{
int x;
cin >> x;
auto e = e0;
for (auto &[w, a, b] : e)
w = abs(w - x);
sort(all(e));
sz.assign(n, 1), dsu = sz;
for (int i = 0; i < n; ++i)
dsu[i] = i;
int ans = 0;
for (auto [w, a, b] : e)
if (f(a) != f(b))
{
un(a, b);
ans += w;
}
cout << ans << '\n';
}
}
/*
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17
*/
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | 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... |