248652026-02-16 09:58:46szabelrLogisztikai központcpp17Elfogadva 50/50101ms17356 KiB
#include <bits/stdc++.h>
using namespace std;

void dfs(int v, int p,
         const vector<vector<pair<int,long long>>> &adj,
         vector<long long> &dist,
         int &far)
{
    for (auto [to, w] : adj[v]) {
        if (to == p) continue;
        dist[to] = dist[v] + w;
        if (dist[to] > dist[far]) far = to;
        dfs(to, v, adj, dist, far);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<pair<int,long long>>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    // 1) 1-ből -> A
    vector<long long> dist(n + 1, 0);
    int A = 1;
    dfs(1, 0, adj, dist, A);

    // 2) A-ból -> B és közben distA
    vector<long long> distA(n + 1, 0);
    int B = A;
    dfs(A, 0, adj, distA, B);

    // 3) B-ből -> distB
    vector<long long> distB(n + 1, 0);
    int dummy = B; // csak hogy a dfs-nek legyen far paramétere, nem érdekes
    dfs(B, 0, adj, distB, dummy);

    // 4) ecc(v) = max(distA[v], distB[v]) minimuma adja T-t és a középpontokat
    long long T = LLONG_MAX;
    vector<int> centers;

    for (int i = 1; i <= n; i++) {
        long long ecc = max(distA[i], distB[i]);
        if (ecc < T) {
            T = ecc;
            centers.clear();
            centers.push_back(i);
        } else if (ecc == T) {
            centers.push_back(i);
        }
    }

    cout << T << "\n";
    cout << centers.size() << "\n";
    for (int x : centers) cout << x << " ";
    cout << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms508 KiB
2Elfogadva0/082ms9264 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/42ms316 KiB
6Elfogadva4/41ms320 KiB
7Elfogadva4/41ms324 KiB
8Elfogadva5/52ms468 KiB
9Elfogadva2/294ms10136 KiB
10Elfogadva2/290ms10108 KiB
11Elfogadva2/21ms500 KiB
12Elfogadva2/22ms564 KiB
13Elfogadva2/24ms820 KiB
14Elfogadva2/27ms1332 KiB
15Elfogadva2/285ms9248 KiB
16Elfogadva2/276ms8828 KiB
17Elfogadva2/279ms9456 KiB
18Elfogadva2/261ms7160 KiB
19Elfogadva2/264ms9620 KiB
20Elfogadva3/3101ms17356 KiB