43302023-03-24 18:14:33gortomiLogisztikai központcpp17Hibás válasz 18/5093ms34824 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)
{
    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);
}
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ÖsszpontTesztVerdiktIdőMemória
base18/50
1Elfogadva0/03ms1768 KiB
2Hibás válasz0/064ms16512 KiB
3Elfogadva4/43ms2140 KiB
4Elfogadva4/43ms2348 KiB
5Hibás válasz0/43ms2564 KiB
6Hibás válasz0/42ms2776 KiB
7Elfogadva4/43ms3000 KiB
8Hibás válasz0/53ms3420 KiB
9Hibás válasz0/265ms19876 KiB
10Elfogadva2/264ms20120 KiB
11Hibás válasz0/23ms3888 KiB
12Elfogadva2/23ms4156 KiB
13Hibás válasz0/24ms4560 KiB
14Hibás válasz0/28ms5124 KiB
15Hibás válasz0/263ms18864 KiB
16Hibás válasz0/259ms18148 KiB
17Hibás válasz0/264ms19664 KiB
18Hibás válasz0/248ms15504 KiB
19Elfogadva2/257ms19972 KiB
20Hibás válasz0/393ms34824 KiB