40132023-03-08 13:21:45tamasmarkLogisztikai központcpp17Time limit exceeded 29/501.1s15888 KiB
// logikai kozpontok.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

struct ut
{
    long long hova, hossz;
};
struct adat
{
    bool lat;
    long long tav = LLONG_MAX,maxi;
    vector<ut>sz;
};
priority_queue<ut>que;
ut akt;
bool operator<(const ut a, const ut b)
{
    return a.hossz > b.hossz;
}
vector<adat>x;
vector<int>megold;
long long n, m, a, b, c,i,maxi,h,mini,j;

int main()
{
    cin >> n;
    x.resize(n + 1);
    for (i = 1; i <= n - 1; ++i)
    {
        cin >> a >> b >> c;
        x[a].sz.push_back({ b,c });
        x[b].sz.push_back({ a,c });
    }
    for (i = 1; i <= n; ++i)
    {
        maxi = -999;
        que.push({ i,0 });
        while (!que.empty())
        {
            akt = que.top();
            while (x[akt.hova].lat && !que.empty())
            {
                que.pop();
                if (!que.empty()) akt = que.top();
            }
            if (que.empty()) break;
            x[akt.hova].lat = true;
            x[akt.hova].tav = akt.hova;
            for (auto& e : x[akt.hova].sz)
            {
                if (!x[e.hova].lat && x[e.hova].tav > akt.hossz + e.hossz)
                {
                    x[e.hova].tav = akt.hossz + e.hossz;
                    if (x[e.hova].tav > maxi)
                    {
                        maxi = x[e.hova].tav;
                        //h = e.hova;
                    }
                    que.push({ e.hova,e.hossz + akt.hossz });
                }
            }
        }
        x[i].maxi = maxi;
        for (j = 1; j <= n; ++j)
        {
            x[j].tav = LLONG_MAX;
            x[j].lat = false;
        }
    }
    mini = 999999;
    for (i = 1; i <= n; ++i)
    {
        if (x[i].maxi < mini)
        {
            mini = x[i].maxi;
            megold.clear();
            megold.push_back(i);
        }
        else if (x[i].maxi == mini) megold.push_back(i);
    }
    cout << mini << "\n";
    cout << megold.size() << "\n";
    sort(megold.begin(), megold.end());
    for (i = 0; i < megold.size(); ++i)
    {
        cout << megold[i] << "\n";
    }
    return 0;
}
/*
10
1 8 4
3 8 5
6 8 3
8 10 6
7 8 2
8 2 9
8 9 2
5 8 6
4 8 2

*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
SubtaskSumTestVerdictTimeMemory
base29/50
1Accepted0/03ms1744 KiB
2Time limit exceeded0/01.1s10476 KiB
3Accepted4/43ms2316 KiB
4Accepted4/43ms2420 KiB
5Accepted4/43ms2636 KiB
6Accepted4/43ms2852 KiB
7Accepted4/44ms2984 KiB
8Accepted5/582ms3152 KiB
9Time limit exceeded0/21.049s12572 KiB
10Time limit exceeded0/21.057s12828 KiB
11Accepted2/224ms3632 KiB
12Accepted2/2142ms3868 KiB
13Time limit exceeded0/21.049s3416 KiB
14Time limit exceeded0/21.07s4028 KiB
15Time limit exceeded0/21.044s12460 KiB
16Time limit exceeded0/21.064s11968 KiB
17Time limit exceeded0/21.077s12744 KiB
18Time limit exceeded0/21.06s10304 KiB
19Time limit exceeded0/21.067s15888 KiB
20Time limit exceeded0/31.054s13056 KiB