148432025-02-04 15:38:46mateHálózati átvitelcpp17Hibás válasz 0/5068ms1556 KiB
#include <bits/stdc++.h>
#include <queue>
using namespace std;

vector <vector <pair<int,int>>> graf;
vector <int> dist;
vector <int> tavok;
vector <int> parent;
int tav = 0;

void bfs(int p, int h){
    priority_queue<pair<int,int>> pq;
    // , vector<pair<int,int>>, greater<pair<int,int>>
    pq.push({INT_MAX,p});
    tavok[p] = INT_MAX;
    parent[p] = p;
    while(!pq.empty()){
        auto csucs = pq.top();
        pq.pop();
        if(dist[parent[csucs.second]] > h + 1){
            continue;
        }
        tavok[csucs.second] = max(min(tavok[parent[csucs.second]],csucs.first),tavok[csucs.second]);
        dist[csucs.second] = dist[parent[csucs.second]] + 1;
        cerr << csucs.second << ' ' << tavok[csucs.second] << '\n';

        

        for(auto x : graf[csucs.second]){
            if(tavok[x.second] == 0){
                
                
                pq.push(x);
                parent[x.second] = csucs.second;
                
                
            }
            //cerr << x.second << ' ' << tavok[x.second] << '\n';

            
        }
        cerr << '\n';
    }
}

int main() {
	int n,m,k,h; cin >> n >> m >> k >> h;
    int a,b,c;
    graf.resize(n+1);
    dist.resize(n+1,0);
    tavok.resize(n+1,0);
    parent.resize(n+1,0);
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        graf[a].push_back({c,b});
        graf[b].push_back({c,a});
    }
    bfs(k, h);
    for(int i = 1; i <=n; i++){
        if(tavok[i] == INT_MAX){
            cout << 0 << '\n';
        }else
        if(tavok[i] == 0){
            cout << -1 << '\n';
        }else
        cout << tavok[i] << '\n';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Elfogadva0/01ms316 KiB
2Hibás válasz0/02ms500 KiB
3Hibás válasz0/11ms316 KiB
4Hibás válasz0/11ms316 KiB
5Hibás válasz0/22ms320 KiB
6Hibás válasz0/22ms316 KiB
7Hibás válasz0/24ms468 KiB
8Hibás válasz0/24ms316 KiB
9Hibás válasz0/14ms316 KiB
10Hibás válasz0/16ms508 KiB
11Hibás válasz0/113ms604 KiB
12Hibás válasz0/118ms692 KiB
13Hibás válasz0/212ms624 KiB
14Hibás válasz0/217ms644 KiB
15Hibás válasz0/234ms848 KiB
16Hibás válasz0/237ms928 KiB
17Hibás válasz0/235ms836 KiB
18Hibás válasz0/234ms820 KiB
19Hibás válasz0/235ms760 KiB
20Hibás válasz0/235ms824 KiB
21Hibás válasz0/127ms1128 KiB
22Hibás válasz0/139ms1260 KiB
23Hibás válasz0/154ms1428 KiB
24Hibás válasz0/159ms1492 KiB
25Hibás válasz0/261ms1484 KiB
26Hibás válasz0/259ms1484 KiB
27Hibás válasz0/268ms1556 KiB
28Hibás válasz0/261ms1532 KiB
29Hibás válasz0/259ms1372 KiB
30Hibás válasz0/259ms1384 KiB
31Hibás válasz0/257ms1520 KiB
32Hibás válasz0/261ms1368 KiB