43292023-03-24 18:00:12gortomiLogisztikai központcpp17Hibás válasz 18/5082ms32692 KiB
#include <bits/stdc++.h>
using namespace std;
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)
{
    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);
}
int 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ÖsszpontTesztVerdiktIdőMemória
base18/50
1Elfogadva0/03ms1892 KiB
2Hibás válasz0/067ms16704 KiB
3Elfogadva4/43ms2328 KiB
4Elfogadva4/43ms2540 KiB
5Hibás válasz0/43ms2716 KiB
6Hibás válasz0/43ms2936 KiB
7Elfogadva4/43ms3152 KiB
8Hibás válasz0/53ms3320 KiB
9Hibás válasz0/271ms19904 KiB
10Elfogadva2/268ms19852 KiB
11Hibás válasz0/23ms3484 KiB
12Elfogadva2/23ms3712 KiB
13Hibás válasz0/24ms4572 KiB
14Hibás válasz0/28ms5020 KiB
15Hibás válasz0/261ms18752 KiB
16Hibás válasz0/257ms18204 KiB
17Hibás válasz0/263ms19808 KiB
18Hibás válasz0/248ms16028 KiB
19Elfogadva2/257ms20204 KiB
20Hibás válasz0/382ms32692 KiB