4719 | 2023. 03. 31 09:57:22 | Erik_Gepard | Hálózati átvitel | cpp17 | Elfogadva 50/50 | 32ms | 6280 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int, int>
int n, m, rajt, cel, h;
struct el{
int a;
int b;
int suly;
};
el e1;
vector<vector<pii> > graf;
void bellman_ford(){
vector<int> d1(n+1, -1);
vector<int> d2(n+1, -1);
d1[rajt]=INT_MAX;
d2[rajt]=INT_MAX;
for(int i=0; i<h; i++){
for(int j=1; j<=n; j++){
for(pii x : graf[j])
if(d1[x.fi]<min(x.se, d2[j])){
d1[x.fi]=min(x.se, d2[j]);
}
}
d2=d1;
}
d1[rajt]=0;
for(int i=1; i<=n; i++){
cout<<d1[i]<<"\n";
}
}
void solve() {
cin>>n>>m>>rajt>>h;
graf.resize(n+1);
for(int i=0; i<m; i++){
int x, y, z;
cin>>x>>y>>z;
graf[x].pb(mp(y, z));
graf[y].pb(mp(x, z));
}
bellman_ford();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1696 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 1888 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 1952 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2216 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2352 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2400 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2760 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 2968 KiB | |||
9 | Elfogadva | 1/1 | 3ms | 2940 KiB | |||
10 | Elfogadva | 1/1 | 4ms | 2964 KiB | |||
11 | Elfogadva | 1/1 | 4ms | 3276 KiB | |||
12 | Elfogadva | 1/1 | 4ms | 3664 KiB | |||
13 | Elfogadva | 2/2 | 4ms | 3476 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 3876 KiB | |||
15 | Elfogadva | 2/2 | 8ms | 4304 KiB | |||
16 | Elfogadva | 2/2 | 8ms | 4528 KiB | |||
17 | Elfogadva | 2/2 | 8ms | 4492 KiB | |||
18 | Elfogadva | 2/2 | 8ms | 4488 KiB | |||
19 | Elfogadva | 2/2 | 8ms | 4640 KiB | |||
20 | Elfogadva | 2/2 | 8ms | 4524 KiB | |||
21 | Elfogadva | 1/1 | 17ms | 5320 KiB | |||
22 | Elfogadva | 1/1 | 20ms | 5552 KiB | |||
23 | Elfogadva | 1/1 | 23ms | 5520 KiB | |||
24 | Elfogadva | 1/1 | 26ms | 5804 KiB | |||
25 | Elfogadva | 2/2 | 30ms | 5952 KiB | |||
26 | Elfogadva | 2/2 | 30ms | 6096 KiB | |||
27 | Elfogadva | 2/2 | 32ms | 6020 KiB | |||
28 | Elfogadva | 2/2 | 17ms | 6268 KiB | |||
29 | Elfogadva | 2/2 | 17ms | 6116 KiB | |||
30 | Elfogadva | 2/2 | 17ms | 6120 KiB | |||
31 | Elfogadva | 2/2 | 17ms | 5988 KiB | |||
32 | Elfogadva | 2/2 | 17ms | 6280 KiB |