1602 | 2022. 11. 28 20:36:04 | kicsiboglar | Hálózati átvitel | cpp11 | Elfogadva 50/50 | 128ms | 23996 KiB |
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#define ll long long
using namespace std;
struct element
{
bool seen = false, ok = false;
vector <pair<ll, ll> > sz;
};
vector <element> x;
ll n, m, k, i, j, a, b, c, start, h;
vector <vector<ll> > y;
bool compare(pair<ll, ll>& a, pair<ll, ll>& b)
{
return a.second > b.second;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> start >> h;
y.resize(n + 1,vector<ll> (h+1,0));
x.resize(n + 1);
for (i = 1; i <= m; ++i)
{
cin >> a >> b >> c;
x[a].sz.push_back({ b,c });
x[b].sz.push_back({ a,c });
}
for (i = 1; i <= n; ++i)
{
sort(x[i].sz.begin(), x[i].sz.end(), compare);
}
deque <pair<ll,ll> > v;
v.push_back({ start,0 });
x[start].ok = true;
y[start][0] = LLONG_MAX;
pair<ll,ll> curr;
while (!v.empty())
{
curr = v[0];
x[curr.first].ok = true;
v.pop_front();
for (auto& e:x[curr.first].sz)
{
if (e.first != start)
{
if (curr.second + 1 <= h)
{
if (y[e.first][curr.second + 1] == 0) v.push_back({ e.first,curr.second + 1 });
y[e.first][curr.second + 1] = max(y[e.first][curr.second + 1], min(y[curr.first][curr.second], e.second));
}
}
}
}
for (i = 1; i <= n; ++i)
{
if (i == start) cout << "0\n";
else if (!x[i].ok) cout << "-1\n";
else
{
ll maxi = 0;
for (j = 1; j <= h; ++j) maxi = max(maxi, y[i][j]);
if (maxi != 0)cout << maxi << "\n";
else cout << "-1\n";
}
}
}
/*
5 5 1 1
1 2 2
1 5 4
1 4 3
5 4 1
5 3 4
10 9 8 1
1 8 4
3 8 5
6 8 3
8 10 6
7 8 2
8 2 9
8 9 2
5 8 6
4 8 2
*/
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1956 KiB | |||
2 | Elfogadva | 0/0 | 2ms | 2268 KiB | |||
3 | Elfogadva | 1/1 | 2ms | 2292 KiB | |||
4 | Elfogadva | 1/1 | 2ms | 2500 KiB | |||
5 | Elfogadva | 2/2 | 2ms | 2588 KiB | |||
6 | Elfogadva | 2/2 | 2ms | 2936 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3264 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3376 KiB | |||
9 | Elfogadva | 1/1 | 3ms | 4012 KiB | |||
10 | Elfogadva | 1/1 | 4ms | 4128 KiB | |||
11 | Elfogadva | 1/1 | 6ms | 4300 KiB | |||
12 | Elfogadva | 1/1 | 6ms | 4436 KiB | |||
13 | Elfogadva | 2/2 | 6ms | 4548 KiB | |||
14 | Elfogadva | 2/2 | 7ms | 4816 KiB | |||
15 | Elfogadva | 2/2 | 13ms | 5700 KiB | |||
16 | Elfogadva | 2/2 | 9ms | 5188 KiB | |||
17 | Elfogadva | 2/2 | 12ms | 5424 KiB | |||
18 | Elfogadva | 2/2 | 16ms | 6140 KiB | |||
19 | Elfogadva | 2/2 | 13ms | 5792 KiB | |||
20 | Elfogadva | 2/2 | 12ms | 5752 KiB | |||
21 | Elfogadva | 1/1 | 52ms | 20132 KiB | |||
22 | Elfogadva | 1/1 | 71ms | 19684 KiB | |||
23 | Elfogadva | 1/1 | 81ms | 19428 KiB | |||
24 | Elfogadva | 1/1 | 92ms | 20500 KiB | |||
25 | Elfogadva | 2/2 | 120ms | 23696 KiB | |||
26 | Elfogadva | 2/2 | 119ms | 23604 KiB | |||
27 | Elfogadva | 2/2 | 128ms | 23996 KiB | |||
28 | Elfogadva | 2/2 | 43ms | 21260 KiB | |||
29 | Elfogadva | 2/2 | 50ms | 23420 KiB | |||
30 | Elfogadva | 2/2 | 48ms | 23576 KiB | |||
31 | Elfogadva | 2/2 | 46ms | 23520 KiB | |||
32 | Elfogadva | 2/2 | 48ms | 23620 KiB |