13202022-05-13 16:55:21nkdorka1212Hálózati átvitelcpp11Hibás válasz 0/50648ms6236 KiB
#include <bits/stdc++.h>

using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int n,m,k,h;
vector<vector<pair<int,int>>>g;
vector<int>vis;
vector<int>dist;
vector<int>seb;

int ok(int c,int w)
{
    queue<int>q;
    q.push(k);
    dist[k]=0;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(auto x:g[v])
        {
            if(x.second>=w && !vis[x.first])
            {
                q.push(x.first);
                dist[x.first]=dist[v]+1;
                vis[x.first]=true;
                seb[x.first]=min(x.second,seb[v]);
            }
        }
    }
    if(vis[c]==0 || dist[c]>h)
    {
        return -1;
    }
    return seb[c];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k>>h;
    g.resize(n+1);
    dist.resize(n+1,0);
    vis.resize(n+1,0);
    seb.resize(n+1,INT_MAX);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int c=1;c<=n;c++)
    {
        vis.assign(n+1,0);
        dist.assign(n+1,-1);
        int l=0,r=10000;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(ok(c,mid)!=-1)
            {
                l=mid;
            }else
            {
                r=mid;
            }
        }
        if(c==k)
        {
            cout<<0<<'\n';
        }else if(l==0)
        {
            cout<<-1<<'\n';
        }else
        {
            cout<<ok(c,l)<<'\n';
        }
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Elfogadva0/02ms1860 KiB
2Hibás válasz0/03ms1936 KiB
3Hibás válasz0/13ms1928 KiB
4Hibás válasz0/11ms1940 KiB
5Hibás válasz0/22ms1964 KiB
6Hibás válasz0/22ms1948 KiB
7Hibás válasz0/22ms2012 KiB
8Hibás válasz0/22ms2020 KiB
9Hibás válasz0/113ms2152 KiB
10Hibás válasz0/135ms2216 KiB
11Hibás válasz0/161ms2392 KiB
12Hibás válasz0/179ms2596 KiB
13Hibás válasz0/261ms2508 KiB
14Hibás válasz0/276ms2700 KiB
15Hibás válasz0/2133ms3044 KiB
16Hibás válasz0/2128ms3176 KiB
17Hibás válasz0/2128ms3304 KiB
18Hibás válasz0/2128ms3448 KiB
19Hibás válasz0/2131ms3588 KiB
20Hibás válasz0/2128ms3724 KiB
21Időlimit túllépés0/1572ms2996 KiB
22Időlimit túllépés0/1597ms3316 KiB
23Időlimit túllépés0/1595ms3568 KiB
24Időlimit túllépés0/1615ms3996 KiB
25Időlimit túllépés0/2596ms4356 KiB
26Időlimit túllépés0/2593ms4672 KiB
27Időlimit túllépés0/2593ms5036 KiB
28Időlimit túllépés0/2625ms5128 KiB
29Időlimit túllépés0/2592ms5416 KiB
30Időlimit túllépés0/2595ms5616 KiB
31Időlimit túllépés0/2596ms6000 KiB
32Időlimit túllépés0/2648ms6236 KiB