43672023-03-27 10:20:14semmiHálózati átvitelcpp17Runtime error 4/5025ms12256 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    
    int n, m, k, h;
    cin >> n >> m >> k >> h;
    vector<vector<pair<int, int>>> adj(100005);
    vector<int> dist(100005, -1), dist2(100005, -1);
    
    dist[k] = INT_MAX;
    dist2[k] = INT_MAX;
    
    for(int i = 0;i < m;i++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    // belman-ford algorithm
    
    for(int i = 0;i < h;i++ ) { //the maximum amount height
        for(int j = 1;j <= n;j++ ) { // using dp and belman ford algorithm
            for(int k = 0;k <= adj[j].size();k++ ) { 
                if(dist[adj[j][k].first] < min(adj[j][k].second, dist2[j])) {
                    dist[adj[j][k].first] = min(adj[j][k].second, dist2[j]);
                    //cout << dist[adj[j][k].first] << ' ' << min(dist[adj[j][k].second], dist2[j])<< endl;
                }
            }
        }
        dist2 = dist;
    }
    dist[k] = 0;
    
    for(int i = 1;i<=n;i++ ) {
        cout << dist[i] << endl;
    }
    
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base4/50
1Accepted0/04ms7972 KiB
2Accepted0/06ms8160 KiB
3Runtime error0/14ms8644 KiB
4Runtime error0/14ms8860 KiB
5Accepted2/26ms8908 KiB
6Accepted2/26ms9120 KiB
7Runtime error0/24ms9380 KiB
8Runtime error0/24ms9264 KiB
9Runtime error0/16ms9572 KiB
10Runtime error0/17ms9540 KiB
11Runtime error0/18ms10152 KiB
12Runtime error0/18ms10228 KiB
13Runtime error0/28ms10452 KiB
14Runtime error0/28ms10364 KiB
15Runtime error0/214ms10392 KiB
16Runtime error0/214ms10536 KiB
17Runtime error0/213ms10692 KiB
18Runtime error0/214ms10700 KiB
19Runtime error0/214ms10772 KiB
20Runtime error0/213ms10720 KiB
21Runtime error0/113ms10864 KiB
22Runtime error0/117ms11484 KiB
23Runtime error0/119ms11644 KiB
24Runtime error0/121ms11692 KiB
25Runtime error0/224ms11864 KiB
26Runtime error0/223ms11944 KiB
27Runtime error0/225ms12088 KiB
28Runtime error0/223ms11996 KiB
29Runtime error0/223ms11992 KiB
30Runtime error0/221ms11996 KiB
31Runtime error0/221ms12000 KiB
32Runtime error0/223ms12256 KiB