4332 | 2023. 03. 24 18:56:31 | gortomi | Logisztikai központ | cpp17 | Elfogadva 50/50 | 82ms | 35120 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<pair<int, long long> > > g;
vector<long long> v;
vector<int> ans;
long long mini = 1e18;
void dfs(int n, int p)
{
for(auto x : g[n])
{
if(x.first != p)
{
dfs(x.first, n);
v[n] = max(v[n], v[x.first] + x.second);
}
}
}
void calc(int n, int p)
{
int a = v[n];
v[n] = 0;
for(auto x : g[n])
{
v[n] = max(v[n], v[x.first] + x.second);
}
int maxp = -1;
for(auto x : g[n])
{
if(v[x.first] + x.second == v[n]) maxp = x.first;
}
for(auto x : g[n])
{
if(x.first == p) continue;
if(x.first != maxp) calc(x.first, n);
else
{
int k = v[n];
v[n] = 0;
for(auto y : g[n])
{
if(y.first != maxp)
{
v[n] = max(v[n], v[y.first] + y.second);
}
}
calc(x.first, n);
v[n] = k;
}
}
if(v[n] < mini)
{
ans.clear();
mini = v[n];
}
if(v[n] == mini) ans.push_back(n);
v[n] = a;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
g.resize(n + 1);
v.resize(n + 1);
for(int i = 0; i < n - 1; i++)
{
int x, y, w;
cin >> x >> y >> w;
g[x].push_back({y, w});
g[y].push_back({x, w});
}
dfs(1, 0);
calc(1, 0);
cout << mini << "\n" << ans.size() << "\n";
sort(ans.begin(), ans.end());
for(auto x : ans) cout << x << " ";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1896 KiB | |||
2 | Elfogadva | 0/0 | 67ms | 16704 KiB | |||
3 | Elfogadva | 4/4 | 3ms | 2332 KiB | |||
4 | Elfogadva | 4/4 | 3ms | 2544 KiB | |||
5 | Elfogadva | 4/4 | 3ms | 2752 KiB | |||
6 | Elfogadva | 4/4 | 3ms | 2936 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 3156 KiB | |||
8 | Elfogadva | 5/5 | 3ms | 3448 KiB | |||
9 | Elfogadva | 2/2 | 65ms | 19736 KiB | |||
10 | Elfogadva | 2/2 | 71ms | 20000 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3592 KiB | |||
12 | Elfogadva | 2/2 | 3ms | 3836 KiB | |||
13 | Elfogadva | 2/2 | 4ms | 4596 KiB | |||
14 | Elfogadva | 2/2 | 8ms | 5488 KiB | |||
15 | Elfogadva | 2/2 | 64ms | 18944 KiB | |||
16 | Elfogadva | 2/2 | 57ms | 18156 KiB | |||
17 | Elfogadva | 2/2 | 64ms | 19800 KiB | |||
18 | Elfogadva | 2/2 | 48ms | 16132 KiB | |||
19 | Elfogadva | 2/2 | 57ms | 20172 KiB | |||
20 | Elfogadva | 3/3 | 82ms | 35120 KiB |