40142023-03-08 13:22:54tamasmarkLogisztikai központcpp17Time limit exceeded 29/501.1s15340 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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/03ms1888 KiB
2Time limit exceeded0/01.1s10468 KiB
3Accepted4/43ms2572 KiB
4Accepted4/42ms2572 KiB
5Accepted4/43ms2544 KiB
6Accepted4/43ms2688 KiB
7Accepted4/44ms2780 KiB
8Accepted5/582ms3000 KiB
9Time limit exceeded0/21.065s12328 KiB
10Time limit exceeded0/21.06s12592 KiB
11Accepted2/223ms3352 KiB
12Accepted2/2140ms3600 KiB
13Time limit exceeded0/21.077s2940 KiB
14Time limit exceeded0/21.052s3772 KiB
15Time limit exceeded0/21.07s11940 KiB
16Time limit exceeded0/21.067s11580 KiB
17Time limit exceeded0/21.065s12240 KiB
18Time limit exceeded0/21.065s9696 KiB
19Time limit exceeded0/21.072s15340 KiB
20Time limit exceeded0/31.062s13124 KiB