9393 | 2024. 02. 21 12:09:52 | csaron71 | Hálózati átvitel | cpp17 | Hibás válasz 0/50 | 37ms | 18616 KiB |
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int main() {
int n, m, k, h;
cin >> n >> m >> k >> h;
vector<vector<pair<int, int> > > elek(n+1, vector<pair<int, int> >());
for (int i=0; i<m; i++) {
int x, y, z;
cin >> x >> y >> z;
elek[x].push_back({y, z});
elek[y].push_back({x, z});
}
vector<vector<int> > tav(n+1, vector<int>(h+1, -10e5-1));
tav[k][0]=10e5+1;
priority_queue<pair<int, pair<int, int> > > sor; //hany, honnan, hova
vector<bool> volt(n+1, false);
volt[k]=true;
sor.push({0, {k, k}});
while (sor.size()>0) {
int messze=sor.top().first;
int honnan=sor.top().second.first;
int hova=sor.top().second.second;
sor.pop();
volt[hova]=true;
//cout << hova << ": ";
for (int i=1; i<h+1; i++) {
tav[hova][i]=max(tav[hova][i], min(messze, tav[honnan][i-1]));
//cout << tav[hova][i] << " ";
}
//cout << "\n";
for (pair<int, int> sz : elek[hova]) {
if (volt[sz.first]==false) {
sor.push({sz.second, {hova, sz.first}});
}
}
}
for (int i=1; i<n+1; i++) {
int epp=-10e5+1;
for (int j=0; j<h+1; j++) {
//cout << tav[i][j]<< " ";
epp=max(epp, tav[i][j]);
}
//cout << epp << "\n";
if (epp==10e5+1) {
cout << "0\n";
}
else {
cout << epp << "\n";
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 0/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Hibás válasz | 0/0 | 3ms | 2096 KiB | |||
3 | Hibás válasz | 0/1 | 3ms | 2292 KiB | |||
4 | Hibás válasz | 0/1 | 3ms | 2460 KiB | |||
5 | Hibás válasz | 0/2 | 3ms | 2692 KiB | |||
6 | Hibás válasz | 0/2 | 3ms | 2780 KiB | |||
7 | Hibás válasz | 0/2 | 4ms | 2896 KiB | |||
8 | Hibás válasz | 0/2 | 4ms | 3232 KiB | |||
9 | Hibás válasz | 0/1 | 4ms | 3412 KiB | |||
10 | Hibás válasz | 0/1 | 4ms | 3704 KiB | |||
11 | Hibás válasz | 0/1 | 7ms | 4112 KiB | |||
12 | Hibás válasz | 0/1 | 8ms | 4488 KiB | |||
13 | Hibás válasz | 0/2 | 7ms | 4464 KiB | |||
14 | Hibás válasz | 0/2 | 8ms | 4632 KiB | |||
15 | Hibás válasz | 0/2 | 14ms | 5440 KiB | |||
16 | Hibás válasz | 0/2 | 14ms | 5352 KiB | |||
17 | Hibás válasz | 0/2 | 14ms | 5576 KiB | |||
18 | Hibás válasz | 0/2 | 16ms | 6120 KiB | |||
19 | Hibás válasz | 0/2 | 14ms | 6020 KiB | |||
20 | Hibás válasz | 0/2 | 14ms | 6184 KiB | |||
21 | Hibás válasz | 0/1 | 19ms | 13312 KiB | |||
22 | Hibás válasz | 0/1 | 25ms | 13764 KiB | |||
23 | Hibás válasz | 0/1 | 29ms | 13896 KiB | |||
24 | Hibás válasz | 0/1 | 34ms | 15024 KiB | |||
25 | Hibás válasz | 0/2 | 35ms | 16836 KiB | |||
26 | Hibás válasz | 0/2 | 35ms | 16716 KiB | |||
27 | Hibás válasz | 0/2 | 37ms | 17424 KiB | |||
28 | Hibás válasz | 0/2 | 29ms | 16200 KiB | |||
29 | Hibás válasz | 0/2 | 32ms | 17800 KiB | |||
30 | Hibás válasz | 0/2 | 30ms | 18016 KiB | |||
31 | Hibás válasz | 0/2 | 30ms | 18352 KiB | |||
32 | Hibás válasz | 0/2 | 32ms | 18616 KiB |