44852023-03-28 15:24:45UnluckYHálózati átvitelcpp11Runtime error 37/50558ms39452 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll INF = 100001;

int main(){

    int n, m, k, h; cin >> n >> m >> k >> h;
    vector<vector<pair<int, int>>> v(n+1);

    for (int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    } 

    vector<vector<int>> d(n+1, vector<int>(h+1, 0));
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({INF, {k, 0}});
    d[k][0] = INF;

    while(!q.empty()){
        int dis = q.top().first;
        int x = q.top().second.first;
        int y = q.top().second.second;
        q.pop();
        if (dis < d[x][y] || y > h) continue;

        for (pair<int, int> i : v[x]){
            if (min(dis, i.second) > d[i.first][y+1]){
                d[i.first][y+1] = min(dis, i.second);
                q.push({d[i.first][y+1], {i.first, y+1}});
            }
        }
    }

    vector<int> dd(n+1, 0);

    //cout << d[3][2] << endl;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= h; j++){
            dd[i] = max(dd[i], d[i][j]);
        }
    }

    dd[k] = 0;



    for (int i = 1; i <= n; i++){
        if (dd[i] == 0 && i != k){
            cout << -1 << endl; continue;
        }
        cout << dd[i] << endl;}

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base37/50
1Accepted0/03ms1808 KiB
2Accepted0/03ms2296 KiB
3Runtime error0/13ms2180 KiB
4Accepted1/13ms2284 KiB
5Accepted2/23ms2392 KiB
6Accepted2/24ms2752 KiB
7Accepted2/24ms2884 KiB
8Accepted2/24ms3096 KiB
9Accepted1/16ms3280 KiB
10Runtime error0/113ms3896 KiB
11Accepted1/121ms4772 KiB
12Accepted1/118ms4724 KiB
13Accepted2/221ms4724 KiB
14Accepted2/224ms4776 KiB
15Runtime error0/254ms7480 KiB
16Runtime error0/232ms6100 KiB
17Accepted2/241ms6208 KiB
18Accepted2/268ms7888 KiB
19Runtime error0/252ms7928 KiB
20Accepted2/243ms8032 KiB
21Runtime error0/1158ms14080 KiB
22Accepted1/1244ms18420 KiB
23Accepted1/1317ms24404 KiB
24Accepted1/1384ms25080 KiB
25Accepted2/2492ms26760 KiB
26Accepted2/2488ms26892 KiB
27Time limit exceeded0/2558ms39096 KiB
28Runtime error0/2375ms37492 KiB
29Accepted2/2448ms39128 KiB
30Accepted2/2432ms39232 KiB
31Accepted2/2414ms39272 KiB
32Accepted2/2456ms39452 KiB