//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo t;
llo par[1000001];
llo par2[1000001];
vector<llo> adj[1000001];
llo it[1000001];
llo find(llo no){
if(par[no]==no){
return par[no];
}
par[no]=find(par[no]);
return par[no];
}
llo co=0;
llo st[1000001];
llo endd[1000001];
llo ss[100001];
llo val[100001];
//llo par2[100001];
void dfs(llo no,llo par=-1){
st[no]=co;
co++;
par2[no]=par;
ss[no]=it[no];
for(auto j:adj[no]){
if(j!=par){
dfs(j,no);
ss[no]+=ss[j];
}
}
endd[no]=co-1;
}
bool ispar(llo x,llo y){
return st[x]<=st[y] and endd[x]>=endd[y];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
llo n,m,k;
cin>>n>>m>>k;
vector<pair<llo,pair<llo,llo>>> ed;
for(llo i=0;i<m;i++){
llo aa,bb,cc;
cin>>aa>>bb>>cc;
aa--;
bb--;
ed.pb({cc,{aa,bb}});
}
sort(ed.begin(),ed.end());
vector<pair<llo,llo>> zz;
for(llo i=0;i<k;i++){
llo aa,bb;
cin>>aa>>bb;
aa--;
bb--;
zz.pb({aa,bb});
}
for(llo i=0;i<n;i++){
cin>>it[i];
}
llo ans=0;
for(llo i=1;i<(1<<k);i++){
for(llo j=0;j<n;j++){
par[j]=j;
adj[i].clear();
}
llo st=1;
for(llo j=0;j<k;j++){
if((1<<j)&i){
llo x=find(zz[j].a);
llo y=find(zz[j].b);
if(x==y){
st=0;
break;
}
par[x]=y;
adj[zz[j].a].pb(zz[j].b);
adj[zz[j].b].pb(zz[j].a);
}
}
if(st==0){
continue;
}
vector<pair<llo,pair<llo,llo>>> dd;
for(auto j:ed){
llo x=find(j.b.a);
llo y=find(j.b.b);
if(x!=y){
par[x]=y;
adj[j.b.a].pb(j.b.b);
adj[j.b.b].pb(j.b.a);
}
else{
dd.pb(j);
}
}
//continue;
co=0;
dfs(0);
for(llo j=0;j<n;j++){
par[j]=par2[j];
val[j]=1e9;
}
//continue;
for(auto j:dd){
llo x=j.b.a;//find(j.b.a);
llo y=j.b.b;//find(j.b.b);
llo cur=x;
vector<llo> xx;
//continue;
if(!ispar(x,y)){
while(!ispar(cur,y)){
xx.pb(cur);
//cout<<cur<<",";
cur=par[cur];
}
//cout<<endl;
}
for(llo ii=0;ii<xx.size();ii++){
val[xx[ii]]=min(val[xx[ii]],j.a);
par[xx[ii]]=cur;
}
cur=y;
xx.clear();
if(!ispar(y,x)){
while(!ispar(cur,x)){
xx.pb(cur);
cur=par[cur];
}
}
for(llo ii=0;ii<xx.size();ii++){
val[xx[ii]]=min(val[xx[ii]],j.a);
par[xx[ii]]=cur;
}
}
llo su=0;
for(llo j=0;j<k;j++){
if((1<<j)&i){
if(ispar(zz[j].a,zz[j].b)){
su+=ss[zz[j].b]*val[zz[j].b];
}
else{
su+=ss[zz[j].a]*val[zz[j].a];
}
}
}
ans=max(ans,su);
}
cout<<ans<<endl;
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:132:19: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(llo ii=0;ii<xx.size();ii++){
| ~~^~~~~~~~~~
toll.cpp:144:19: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(llo ii=0;ii<xx.size();ii++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 3 |
Runtime error |
176 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 3 |
Runtime error |
176 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 3 |
Runtime error |
176 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 3 |
Runtime error |
176 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
