| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1155238 | NeilP | Toll (APIO13_toll) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge{
int a;
int b;
int cost;
};
int n, m, k;
vector<vector<pair<int, int>>> tree;
bool comp(Edge a, Edge b){
return a.cost < b.cost;
}
vector<int> parent;
vector<int> size;
vector<int> tots;
int find(int x){
if(parent[x] == x)
return x;
else
{
return (parent[x] = find(parent[x]));
}
}
void merge(int x, int y){
int xh = find(x);
int yh = find(y);
if(xh == yh)
return;
if(size[xh] > size[yh])
swap(xh, yh);
parent[xh] = yh;
size[yh] += size[xh];
}
pair<long long, long long> dfs(int x, int p) // (size, money)
{
pair<long long, long long> tot = {tots[x], 0};
for(pair<int, int> q: tree[x]){
if(q.first == p){
continue;
}
pair<long long, long long> res = dfs(q.first, x);
tot.first += res.first;
tot.second += 1LL * q.second * res.first;
}
return tot;
}
int main()
{
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
parent.push_back(i);
size.push_back(1);
}
int start[20], end[20], toll[20];
vector<Edge> edges;
for(int i = 0; i < m; i++){
int u, v, c;
cin >> u >> v >> c;
u--;
v--;
Edge e = {u, v, c};
edges.push_back(e);
}
sort(edges.begin(), edges.end(), comp);
for(int i = 0; i < k; i++){
cin >> start[i] >> end[i];
start[i]--;
end[i]--;
}
tots = vector<int>(n);
for(int i = 0; i < n; i++)
cin >> tots[i];
tree = vector<vector<pair<int, int>>>(n);
for(Edge e : edges){
int x_comp = find(e.a);
int y_comp = find(e.b);
if(x_comp == y_comp)
continue;
for(int i = 0; i < k; i++){
int u_c = find(start[i]);
int v_c = find(end[i]);
if((u_c == x_comp && v_c == y_comp) || (v_c == x_comp && u_c == y_comp)){
toll[i] = e.cost;
tree[start[i]].push_back({end[i], toll[i]});
tree[end[i]].push_back({start[i], toll[i]});
merge(x_comp, y_comp);
break;
}
}
x_comp = find(e.a);
y_comp = find(e.b);
if(x_comp == y_comp)
continue;
merge(x_comp, y_comp);
tree[e.a].push_back({e.b, 0});
tree[e.b].push_back({e.a, 0});
}
pair<int, int> res = dfs(0, -1);
cout << res.second << endl;
return 0;
}