16022022-11-28 20:36:04kicsiboglarHálózati átvitelcpp11Elfogadva 50/50128ms23996 KiB

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#define ll long long 

using namespace std;

struct element
{
    bool seen = false, ok = false;
    vector <pair<ll, ll> > sz;
};
vector <element> x;
ll n, m, k, i, j, a, b, c, start, h;
vector <vector<ll> > y;

bool compare(pair<ll, ll>& a, pair<ll, ll>& b)
{
    return a.second > b.second;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> start >> h;
    y.resize(n + 1,vector<ll> (h+1,0));
    x.resize(n + 1);
    for (i = 1; i <= m; ++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)
    {
        sort(x[i].sz.begin(), x[i].sz.end(), compare);
        
    }

    deque <pair<ll,ll> > v;
    v.push_back({ start,0 });
    x[start].ok = true;
    y[start][0] = LLONG_MAX;
    pair<ll,ll> curr;
    while (!v.empty())
    {
        curr = v[0];
        x[curr.first].ok = true;
        v.pop_front();
        for (auto& e:x[curr.first].sz)
        {
            if (e.first != start)
            {
                if (curr.second + 1 <= h)
                {
                    if (y[e.first][curr.second + 1] == 0) v.push_back({ e.first,curr.second + 1 });
                    y[e.first][curr.second + 1] = max(y[e.first][curr.second + 1], min(y[curr.first][curr.second], e.second));


                }
            }
        }
    }



    
    for (i = 1; i <= n; ++i)
    {
        if (i == start) cout << "0\n";
        else if (!x[i].ok) cout << "-1\n";
        else
        {
            ll maxi = 0;
            for (j = 1; j <= h; ++j) maxi = max(maxi, y[i][j]);
            if (maxi != 0)cout << maxi << "\n";
            else cout << "-1\n";
        }
    }
}
/*
5 5 1 1
1 2 2
1 5 4
1 4 3
5 4 1
5 3 4


10 9 8 1
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

*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1956 KiB
2Elfogadva0/02ms2268 KiB
3Elfogadva1/12ms2292 KiB
4Elfogadva1/12ms2500 KiB
5Elfogadva2/22ms2588 KiB
6Elfogadva2/22ms2936 KiB
7Elfogadva2/23ms3264 KiB
8Elfogadva2/23ms3376 KiB
9Elfogadva1/13ms4012 KiB
10Elfogadva1/14ms4128 KiB
11Elfogadva1/16ms4300 KiB
12Elfogadva1/16ms4436 KiB
13Elfogadva2/26ms4548 KiB
14Elfogadva2/27ms4816 KiB
15Elfogadva2/213ms5700 KiB
16Elfogadva2/29ms5188 KiB
17Elfogadva2/212ms5424 KiB
18Elfogadva2/216ms6140 KiB
19Elfogadva2/213ms5792 KiB
20Elfogadva2/212ms5752 KiB
21Elfogadva1/152ms20132 KiB
22Elfogadva1/171ms19684 KiB
23Elfogadva1/181ms19428 KiB
24Elfogadva1/192ms20500 KiB
25Elfogadva2/2120ms23696 KiB
26Elfogadva2/2119ms23604 KiB
27Elfogadva2/2128ms23996 KiB
28Elfogadva2/243ms21260 KiB
29Elfogadva2/250ms23420 KiB
30Elfogadva2/248ms23576 KiB
31Elfogadva2/246ms23520 KiB
32Elfogadva2/248ms23620 KiB