44652023-03-28 11:50:49UnluckYHálózati átvitelcpp11Futási hiba 32/50566ms39196 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++){cout << dd[i] << endl;}

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/03ms2052 KiB
3Futási hiba0/13ms2252 KiB
4Hibás válasz0/13ms2372 KiB
5Elfogadva2/23ms2600 KiB
6Elfogadva2/24ms2716 KiB
7Elfogadva2/24ms2988 KiB
8Elfogadva2/24ms3192 KiB
9Hibás válasz0/17ms3712 KiB
10Futási hiba0/113ms4204 KiB
11Elfogadva1/123ms4956 KiB
12Elfogadva1/118ms4732 KiB
13Elfogadva2/223ms4988 KiB
14Elfogadva2/225ms5112 KiB
15Futási hiba0/256ms7908 KiB
16Futási hiba0/232ms6288 KiB
17Elfogadva2/243ms6336 KiB
18Elfogadva2/271ms8068 KiB
19Futási hiba0/254ms8140 KiB
20Elfogadva2/245ms8236 KiB
21Futási hiba0/1162ms14116 KiB
22Hibás válasz0/1245ms18688 KiB
23Hibás válasz0/1321ms24752 KiB
24Hibás válasz0/1398ms25356 KiB
25Elfogadva2/2509ms27008 KiB
26Elfogadva2/2505ms26984 KiB
27Időlimit túllépés0/2566ms21268 KiB
28Futási hiba0/2386ms37816 KiB
29Elfogadva2/2458ms39196 KiB
30Elfogadva2/2444ms39140 KiB
31Elfogadva2/2426ms39140 KiB
32Elfogadva2/2469ms39148 KiB