#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int>fin;
void dfs(int st,vector<array<int,3>>(&g)[],int p, vector<int>(&pars)){
if(st==n-1){
for(int i : pars){
fin.push_back(i);
}
}
for(array<int,3>e:g[st]){
if(e[0]==p)
continue;
pars.push_back(e[2]);
dfs(e[0],g,st,pars);
assert(pars.back()==e[2]);
pars.pop_back();
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
assert(m==n-1);
vector<array<int,3>>g[n];
array<int,3>edges[m];
for(int i = 0;i<m;i++){
cin >> edges[i][0];
cin >> edges[i][1];
cin >> edges[i][2];
edges[i][0]--;
edges[i][1]--;
g[edges[i][0]].push_back({edges[i][1],edges[i][2],i});
g[edges[i][1]].push_back({edges[i][0],edges[i][2],i});
}
long long pref[m];
pref[m-1]=edges[m-1][2];
for(int i = m-2;i>=0;i--){
pref[i]=max(1LL*edges[i][2],pref[i+1]);
}
vector<int>temp;
dfs(0,g,-1,temp);
long long ans = 0;
for(int i : fin){
ans+=edges[i][2];
}
long long maxima = 0;
for(int i : fin){
if(i!=m-1)
maxima=max(maxima,pref[i+1]);
}
ans+=maxima;
cout << ans;
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |