4405 | 2023. 03. 27 17:21:43 | horvathabel | Hálózati átvitel | cpp17 | Accepted 50/50 | 63ms | 13460 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int, int>,int>> g;
bool seen[100001];
int main() {
int n,m,k,h;
cin>>n>>m>>k>>h;
for (int i=0; i<m;i++){
int x,y,c;
cin>>x>>y>>c;
g.push_back({{x,y},c});
}
vector<vector<int>> dp;
dp.resize(n+1,vector<int>(h+1,0));
dp[k][0]=1e9;
for (int j=1; j<=h;j++){
for (int i=1; i<=n;i++) dp[i][j]=dp[i][j-1];
for (pair<pair<int,int>, int> edge:g){
dp[edge.first.first][j]=max(dp[edge.first.first][j],min(dp[edge.first.second][j-1],edge.second));
dp[edge.first.second][j]=max(dp[edge.first.second][j],min(dp[edge.first.first][j-1],edge.second));
}
}
for (int i=1; i<=n;i++){
if (i==k) cout<<0<<endl;
else{
if (dp[i][h]==0) cout<<-1<<endl;
else cout<<dp[i][h]<<endl;
}
}
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Accepted | 0/0 | 3ms | 1820 KiB | |||
2 | Accepted | 0/0 | 3ms | 2024 KiB | |||
3 | Accepted | 1/1 | 3ms | 2360 KiB | |||
4 | Accepted | 1/1 | 3ms | 2384 KiB | |||
5 | Accepted | 2/2 | 3ms | 2596 KiB | |||
6 | Accepted | 2/2 | 3ms | 2680 KiB | |||
7 | Accepted | 2/2 | 4ms | 2952 KiB | |||
8 | Accepted | 2/2 | 3ms | 2908 KiB | |||
9 | Accepted | 1/1 | 4ms | 3404 KiB | |||
10 | Accepted | 1/1 | 4ms | 3484 KiB | |||
11 | Accepted | 1/1 | 7ms | 3784 KiB | |||
12 | Accepted | 1/1 | 8ms | 4032 KiB | |||
13 | Accepted | 2/2 | 8ms | 4060 KiB | |||
14 | Accepted | 2/2 | 9ms | 4212 KiB | |||
15 | Accepted | 2/2 | 14ms | 4420 KiB | |||
16 | Accepted | 2/2 | 14ms | 4328 KiB | |||
17 | Accepted | 2/2 | 14ms | 4648 KiB | |||
18 | Accepted | 2/2 | 16ms | 4748 KiB | |||
19 | Accepted | 2/2 | 14ms | 4704 KiB | |||
20 | Accepted | 2/2 | 14ms | 4772 KiB | |||
21 | Accepted | 1/1 | 41ms | 11764 KiB | |||
22 | Accepted | 1/1 | 48ms | 11824 KiB | |||
23 | Accepted | 1/1 | 43ms | 11424 KiB | |||
24 | Accepted | 1/1 | 46ms | 11772 KiB | |||
25 | Accepted | 2/2 | 52ms | 13348 KiB | |||
26 | Accepted | 2/2 | 59ms | 13308 KiB | |||
27 | Accepted | 2/2 | 63ms | 13336 KiB | |||
28 | Accepted | 2/2 | 61ms | 12288 KiB | |||
29 | Accepted | 2/2 | 56ms | 13324 KiB | |||
30 | Accepted | 2/2 | 54ms | 13340 KiB | |||
31 | Accepted | 2/2 | 54ms | 13308 KiB | |||
32 | Accepted | 2/2 | 56ms | 13460 KiB |