#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 505;
struct DSU {
int parent[maxN], sz[maxN];
void reset(){
for(int x=0;x<maxN;x++){
parent[x] = x;
sz[x] = 1;
}
}
int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
bool merge(int x, int y){
int a = getParent(x);
int b = getParent(y);
if(a != b){
if(sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
return false;
}
};
DSU dsu;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<ll, 3>> edge;
for(int x=0;x<m;x++){
ll a, b, w;
cin >> a >> b >> w;
a--; b--;
edge.push_back({w, a, b});
}
sort(edge.begin(), edge.end());
int q;
cin >> q;
ll val[q];
for(int x=0;x<q;x++){
cin >> val[x];
}
array<ll, 4> left[m], right[m];
for(int x=0;x<m;x++){
dsu.reset();
right[x][1] = right[x][2] = right[x][3] = 0;
if(x+1 < m){
right[x][0] = (edge[x][0]+edge[x+1][0])/2;
} else {
right[x][0] = edge[x][0];
}
int cnt = n;
int l = x, r = x+1;
while(cnt > 1){
if(l >= 0 && r < edge.size()){
if(right[x][0]-edge[l][0] <= edge[r][0]-right[x][0]){
if(dsu.merge(edge[l][1], edge[l][2])){
cnt--;
right[x][1] += right[x][0]-edge[l][0];
if(right[x][0]-edge[l][0] != 0) right[x][2]--;
else right[x][3]++;
}
l--;
} else {
if(dsu.merge(edge[r][1], edge[r][2])){
cnt--;
right[x][1] += edge[r][0]-right[x][0];
if(edge[r][0]-right[x][0] != 0) right[x][2]++;
else right[x][3]++;
}
r++;
}
} else if(l >= 0){
if(dsu.merge(edge[l][1], edge[l][2])){
cnt--;
right[x][1] += right[x][0]-edge[l][0];
if(right[x][0]-edge[l][0] != 0) right[x][2]--;
else right[x][3]++;
}
l--;
} else if(r < edge.size()){
if(dsu.merge(edge[r][1], edge[r][2])){
cnt--;
right[x][1] += edge[r][0]-right[x][0];
if(edge[r][0]-right[x][0] != 0) right[x][2]++;
else right[x][3]++;
}
r++;
}
}
dsu.reset();
left[x][1] = left[x][2] = left[x][3] = 0;
if(x > 0){
left[x][0] = min((edge[x][0]+edge[x-1][0])/2 + 1, edge[x][0]);
} else {
left[x][0] = edge[x][0];
}
cnt = n;
l = x-(left[x][0] < edge[x][0]), r = x+1-(left[x][0] < edge[x][0]);
while(cnt > 1){
if(l >= 0 && r < edge.size()){
assert(edge[r][0]-left[x][0] >= 0);
if(left[x][0]-edge[l][0] <= edge[r][0]-left[x][0]){
if(dsu.merge(edge[l][1], edge[l][2])){
cnt--;
left[x][1] += left[x][0]-edge[l][0];
if(left[x][0]-edge[l][0] != 0) left[x][2]--;
else left[x][3]++;
}
l--;
} else {
if(dsu.merge(edge[r][1], edge[r][2])){
cnt--;
left[x][1] += edge[r][0]-left[x][0];
if(edge[r][0]-left[x][0] != 0) left[x][2]++;
else left[x][3]++;
}
r++;
}
} else if(l >= 0){
if(dsu.merge(edge[l][1], edge[l][2])){
cnt--;
left[x][1] += left[x][0]-edge[l][0];
if(left[x][0]-edge[l][0] != 0) left[x][2]--;
else left[x][3]++;
}
l--;
} else if(r < edge.size()){
if(dsu.merge(edge[r][1], edge[r][2])){
cnt--;
left[x][1] += edge[r][0]-left[x][0];
if(edge[r][0]-left[x][0] != 0) left[x][2]++;
else left[x][3]++;
}
r++;
}
}
// cout << edge[x][0] << "-- " << right[x][0] << " " << left[x][0] << "\n";
// cout << right[x][1] << " " << left[x][1] << "\n";
// cout << right[x][2] << " " << left[x][2] << "\n";
// cout << right[x][3] << " " << left[x][3] << "\n";
}
int pos = -1;
for(int x=0;x<q;x++){
while(pos+1 < m && edge[pos+1][0] <= val[x]){
pos++;
}
ll ans = 1e18;
if(pos >= 0){
if(val[x] <= right[pos][0]){
if(edge[pos][0] <= val[x]) ans = min(ans, right[pos][1]+right[pos][2]*abs(val[x]-right[pos][0])+right[pos][3]*abs(val[x]-right[pos][0]));
if(val[x] <= edge[pos][0]) ans = min(ans, left[pos][1]+left[pos][2]*abs(val[x]-left[pos][0])+left[pos][3]*abs(val[x]-left[pos][0]));
} else {
if(edge[pos][0] <= val[x]) ans = min(ans, right[pos][1]+right[pos][2]*abs(val[x]-right[pos][0])*-1+right[pos][3]*abs(val[x]-right[pos][0]));
if(val[x] <= edge[pos][0]) ans = min(ans, left[pos][1]+left[pos][2]*abs(val[x]-left[pos][0])*-1+left[pos][3]*abs(val[x]-left[pos][0]));
}
}
if(pos+1 < m){
if(val[x] <= right[pos+1][0]){
if(edge[pos+1][0] <= val[x]) ans = min(ans, right[pos+1][1]+right[pos+1][2]*abs(val[x]-right[pos+1][0])+right[pos+1][3]*abs(val[x]-right[pos+1][0]));
if(val[x] <= edge[pos+1][0]) ans = min(ans, left[pos+1][1]+left[pos+1][2]*abs(val[x]-left[pos+1][0])+left[pos+1][3]*abs(val[x]-left[pos+1][0]));
} else {
if(edge[pos+1][0] <= val[x]) ans = min(ans, right[pos+1][1]+right[pos+1][2]*abs(val[x]-right[pos+1][0])*-1+right[pos+1][3]*abs(val[x]-right[pos+1][0]));
if(val[x] <= edge[pos+1][0]) ans = min(ans, left[pos+1][1]+left[pos+1][2]*abs(val[x]-left[pos+1][0])*-1+left[pos+1][3]*abs(val[x]-left[pos+1][0]));
}
// ans = min(ans, right[pos+1][1]+right[pos+1][2]*abs(val[x]-right[pos+1][0])*(val[x] <= right[pos+1][0] ? 1 : -1)+right[pos+1][3]*abs(val[x]-right[pos+1][0]));
// ans = min(ans, left[pos+1][1]+left[pos+1][2]*(val[x]-left[pos+1][0])*(val[x] <= left[pos+1][0] ? 1 : -1)+left[pos+1][3]*abs(val[x]-left[pos+1][0]));
}
cout << ans << "\n";
// cout << ans << " " << pos << "\n";
// cout << ans <<","<< pos << " " << " " << right[pos][0] << "-" << right[pos][1] << " " << right[pos][2] << "-" << right[pos][3] << " " << left[pos+1][0] << "-" << left[pos+1][1] << " " << left[pos+1][2] << "\n";
}
return 0;
}
Compilation message
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(l >= 0 && r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | } else if(r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(l >= 0 && r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:158:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | } else if(r < edge.size()){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
