This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
vector<int> path, fpath;
void DFS(int head, int par, vector<vector<pair<int, int>>> &tree){
if(head == tree.size()-1){
fpath = path;
return;
}
for(auto[l, r] : tree[head]){
if(l != par){
path.push_back(r);
DFS(l, head, tree);
path.pop_back();
}
}
}
signed main(){
int N, M;
cin >> N >> M;
vector<vector<pair<int, int>>> tree(N);
vector<int> vals(M);
for(int i = 0; i < M; i ++){
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
tree[a].push_back({b,i});
tree[b].push_back({a,i});
vals[i] = c;
}
if(M == N - 1){
vector<int> maxsuff(N);
for(int i = N-2; i >= 0; i --){
maxsuff[i] = max(vals[i+1], maxsuff[i+1]);
}
DFS(0, -1, tree);
int ans = 0;
for(int i : fpath){
ans = max(ans, maxsuff[i]);
}
for(int i : fpath){
ans += vals[i];
}
cout << ans << endl;
}
else if(*max_element(vals.begin(), vals.end()) == 1){
vector<int> reach(N, 0);
vector<int> md(N, -1);
queue<vector<int>> que;
que.push({0, 0});
while(!que.empty()){
int a = que.front()[0], b = que.front()[1];
que.pop();
if(md[b] == -1){
md[b] = a;
for(auto[l, r] : tree[b]){
que.push({a+1, l});
}
}
if(md[b] == a){
reach[b]++;
}
}
vector<int> dist(md.back()+1);
for(int i = 0; i < N; i ++){
dist[md[i]] += reach[i];
}
bool add = true;
dist[0] = 2;
dist.back() = 2;
for(int i :dist){
if(i < 2)add = false;
}
if(add){
cout << md.back() << endl;
}
else{
cout << md.back() + 1 << endl;
}
}
else{
int an = 0;
for(int i = 0; i < M-1; i ++){
int tval = *max_element(vals.begin()+i+1, vals.end());
vals[i] += tval;
priority_queue<vector<int>> que;
que.push({0,0});
int ans = 0;
vector<bool> vis(N);
while(!que.empty()){
int a = -que.top()[0], b = que.top()[1];
que.pop();
if(b == N-1){ans = a; break;}
if(vis[b])continue;
vis[b] = true;
for(auto [l, r] : tree[b]){
que.push({-a-vals[r], l});
}
}
an = max(an, ans);
vals[i] -= tval;
}
cout << an << endl;
}
return 0;
}
Compilation message (stderr)
Aesthetic.cpp: In function 'void DFS(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
Aesthetic.cpp:10:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | if(head == tree.size()-1){
| ~~~~~^~~~~~~~~~~~~~~~
# | 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... |