#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<long long> freq;
long long ans;
class Edge{
public:
int s, e, c;
bool my;
Edge(int x, int y, int z, bool q){
s = x;
e = y;
c = z;
my = q;
}
bool operator<(const Edge &o) const{
if(c!=o.c){
return c<o.c;
}
return (my!=o.my?my:false);
}
};
vector<Edge> edges;
vector<Edge> adj[100000];
pair<long long, long long> go2(int now, int from){
pair<long long, long long> ret = make_pair(freq[now],0LL);
for(int i = 0; i<adj[now].size(); i++){
Edge ed = adj[now][i];
if(ed.e==from){
continue;
}
pair<long long, long long> got = go2(ed.e,now);
ret.first += got.first;
ret.second += got.second + (ed.my?(long long)ed.c*(long long)got.first:0LL);
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 0; i<m; i++){
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
edges.push_back(Edge(a,b,c, false));
}
vector<Edge> other;
for(int i = 0; i<k; i++){
int a, b;
cin >> a >> b;
a--;
b--;
other.push_back(Edge(a,b,-1, true));
}
for(int i = 0; i<n; i++){
long long x;
cin >> x;
freq.push_back(x);
}
bool assigned[k];
for(int i = 0; i<k; i++){
assigned[i] = false;
}
int comp[n];
int sz[n];
ans = 0LL;
vector<int> li[n];
for(int i = 0; i<n; i++){
comp[i] = i;
sz[i] = 1;
li[i].push_back(i);
}
sort(edges.begin(),edges.end());
vector<Edge> og;
for(int i = 0; i<m; i++){
int ca = comp[edges[i].s];
int cb = comp[edges[i].e];
if(ca==cb){
continue;
}
if(sz[ca]>sz[cb]){
swap(ca,cb);
}
//ca < cb
sz[cb] += sz[ca];
for(int i = 0; i<li[ca].size(); i++){
int now = li[ca][i];
comp[now] = cb;
li[cb].push_back(now);
}
li[ca].clear();
for(int j = 0; j<k; j++){
if(!assigned[j] && comp[other[j].s]==comp[other[j].e]){
assigned[j] = true;
other[j].c = edges[i].c;
}
}
og.push_back(edges[i]);
}
for(int i = 0; i<k; i++){
assert(assigned[i]);
}
for(int z = 0; z<(1<<k); z++){
vector<Edge> all;
vector<Edge> used;
for(int i = 0; i<k; i++){
if(((1<<i)&z)!=0){
all.push_back(other[i]);
}
}
for(int i = 0; i<og.size(); i++){
all.push_back(og[i]);
}
sort(all.begin(),all.end());
for(int i = 0; i<n; i++){
comp[i] = i;
sz[i] = 1;
li[i].clear();
li[i].push_back(i);
}
for(int i = 0; i<all.size(); i++){
int ca = comp[all[i].s];
int cb = comp[all[i].e];
if(ca==cb){
continue;
}
if(sz[ca]>sz[cb]){
swap(ca,cb);
}
//ca < cb
sz[cb] += sz[ca];
for(int i = 0; i<li[ca].size(); i++){
int now = li[ca][i];
comp[now] = cb;
li[cb].push_back(now);
}
li[ca].clear();
used.push_back(all[i]);
}
for(int i = 0; i<n; i++){
adj[i].clear();
}
for(int i = 0; i<used.size(); i++){
Edge ed = used[i];
adj[ed.s].push_back(Edge(ed.s,ed.e,ed.c,ed.my));
adj[ed.e].push_back(Edge(ed.e,ed.s,ed.c,ed.my));
}
ans = max(ans,go2(0,-1).second);
}
cout << ans << endl;
}
Compilation message
toll.cpp: In function 'std::pair<long long int, long long int> go2(int, int)':
toll.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
^
toll.cpp: In function 'int main()':
toll.cpp:88:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<li[ca].size(); i++){
^
toll.cpp:113:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<og.size(); i++){
^
toll.cpp:123:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<all.size(); i++){
^
toll.cpp:134:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<li[ca].size(); i++){
^
toll.cpp:146:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<used.size(); i++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2784 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2784 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2784 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2784 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
