4486 | 2023. 03. 28 15:27:01 | UnluckY | Hálózati átvitel | cpp11 | Elfogadva 50/50 | 549ms | 39792 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 2084 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2180 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2368 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2384 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2496 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 2880 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 3196 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3320 KiB | |||
9 | Elfogadva | 1/1 | 6ms | 3848 KiB | |||
10 | Elfogadva | 1/1 | 12ms | 4312 KiB | |||
11 | Elfogadva | 1/1 | 20ms | 5084 KiB | |||
12 | Elfogadva | 1/1 | 17ms | 5112 KiB | |||
13 | Elfogadva | 2/2 | 20ms | 5076 KiB | |||
14 | Elfogadva | 2/2 | 21ms | 5220 KiB | |||
15 | Elfogadva | 2/2 | 54ms | 7968 KiB | |||
16 | Elfogadva | 2/2 | 32ms | 6616 KiB | |||
17 | Elfogadva | 2/2 | 41ms | 6856 KiB | |||
18 | Elfogadva | 2/2 | 67ms | 8748 KiB | |||
19 | Elfogadva | 2/2 | 52ms | 8760 KiB | |||
20 | Elfogadva | 2/2 | 41ms | 7116 KiB | |||
21 | Elfogadva | 1/1 | 164ms | 14848 KiB | |||
22 | Elfogadva | 1/1 | 237ms | 19280 KiB | |||
23 | Elfogadva | 1/1 | 307ms | 25488 KiB | |||
24 | Elfogadva | 1/1 | 377ms | 25852 KiB | |||
25 | Elfogadva | 2/2 | 486ms | 27500 KiB | |||
26 | Elfogadva | 2/2 | 486ms | 27424 KiB | |||
27 | Elfogadva | 2/2 | 549ms | 39792 KiB | |||
28 | Elfogadva | 2/2 | 384ms | 38184 KiB | |||
29 | Elfogadva | 2/2 | 437ms | 39776 KiB | |||
30 | Elfogadva | 2/2 | 458ms | 39676 KiB | |||
31 | Elfogadva | 2/2 | 407ms | 39484 KiB | |||
32 | Elfogadva | 2/2 | 449ms | 39604 KiB |