4339 | 2023. 03. 25 15:49:52 | szil | Hálózati átvitel | cpp14 | Elfogadva 50/50 | 24ms | 12444 KiB |
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int MAXN = 10001;
struct Edge {
int a, b, w;
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k, h;
cin >> n >> m >> k >> h;
vector<Edge> edges;
for (int i = 0; i < m; i++) {
Edge e;
cin >> e.a >> e.b >> e.w;
edges.push_back(e);
}
vector<vector<int>> d(h+1, vector<int>(MAXN, INT_MIN));
d[0][k] = INT_MAX;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= n; j++) d[i][j] = d[i-1][j];
for (Edge e : edges) {
if (d[i][e.a] != INT_MIN)
d[i][e.b] = max(d[i][e.b], min(d[i-1][e.a],e.w));
if (d[i][e.b] != INT_MIN)
d[i][e.a] = max(d[i][e.a], min(d[i-1][e.b],e.w));
}
}
for (int i = 1; i <= n; i++) {
if (d[h][i] < -1000000) {
cout << "-1\n";
} else {
cout << (i==k?0:d[h][i]) << "\n";
}
}
cout << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 2248 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2712 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2604 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 3456 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 3288 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 3688 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3516 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3580 KiB | |||
9 | Elfogadva | 1/1 | 4ms | 4356 KiB | |||
10 | Elfogadva | 1/1 | 4ms | 5044 KiB | |||
11 | Elfogadva | 1/1 | 4ms | 5480 KiB | |||
12 | Elfogadva | 1/1 | 4ms | 4960 KiB | |||
13 | Elfogadva | 2/2 | 4ms | 5836 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 5552 KiB | |||
15 | Elfogadva | 2/2 | 8ms | 7212 KiB | |||
16 | Elfogadva | 2/2 | 7ms | 5736 KiB | |||
17 | Elfogadva | 2/2 | 8ms | 6776 KiB | |||
18 | Elfogadva | 2/2 | 9ms | 8500 KiB | |||
19 | Elfogadva | 2/2 | 8ms | 7468 KiB | |||
20 | Elfogadva | 2/2 | 8ms | 6936 KiB | |||
21 | Elfogadva | 1/1 | 14ms | 10820 KiB | |||
22 | Elfogadva | 1/1 | 14ms | 10396 KiB | |||
23 | Elfogadva | 1/1 | 17ms | 10348 KiB | |||
24 | Elfogadva | 1/1 | 18ms | 10624 KiB | |||
25 | Elfogadva | 2/2 | 21ms | 12440 KiB | |||
26 | Elfogadva | 2/2 | 21ms | 12400 KiB | |||
27 | Elfogadva | 2/2 | 24ms | 12332 KiB | |||
28 | Elfogadva | 2/2 | 19ms | 11300 KiB | |||
29 | Elfogadva | 2/2 | 21ms | 12444 KiB | |||
30 | Elfogadva | 2/2 | 20ms | 12328 KiB | |||
31 | Elfogadva | 2/2 | 21ms | 12332 KiB | |||
32 | Elfogadva | 2/2 | 21ms | 12372 KiB |