fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define lld long double
  3. #define iint int
  4. #define int long long
  5. #define logArr(arr) for(auto i:arr) cout<<i<<' ';
  6. #define logArr2D(arr) for (auto i:arr) {for(auto j:i)cout<<j<<' ';cout<<endl;}
  7. #define readArr(arr) for(auto &i : arr) cin>>i;
  8. #define allArr(arr) arr.begin(), arr.end()
  9. //#define ONLINE_JUDGE true;
  10. using namespace std;
  11. int n, exch, mn, received;
  12. const long long INF = 2e18;
  13.  
  14. long long dfs(int u, vector<set<pair<int, int>>>& reverse_adj, vector<int>& state, vector<int>& dp) {
  15.    if (state[u] == 1) return INF;
  16.  
  17.    if (state[u] == 2) return dp[u];
  18.  
  19.    state[u] = 1;
  20.    long long max_effort = 0;
  21.  
  22.    for (auto& edge : reverse_adj[u]) {
  23.       int v = edge.first;
  24.       long long weight = edge.second;
  25.  
  26.       long long effort = dfs(v, reverse_adj, state, dp);
  27.  
  28.       if (effort == INF) {
  29.          max_effort = INF;
  30.          break;
  31.       }
  32.       max_effort = max(max_effort, effort + weight);
  33.    }
  34.  
  35.    state[u] = 2;
  36.    dp[u] = max_effort;
  37.    return max_effort;
  38. }
  39. void solve(){
  40.    cin>>n>>exch>>mn>>received;
  41.    vector<set<pair<int, int>>> gf(n+1);
  42.    vector<int> vis(n+1), dp(n+1);
  43.    vector<int> mxcost(n+1);
  44.  
  45.    while(exch--){
  46.       int u, v, c; cin>>u>>v>>c;
  47.       gf[v].insert({u, c});
  48.    }
  49.    int res = dfs(received, gf, vis, dp);
  50.    if(res>=mn)
  51.       cout<<"YES"<<endl;
  52.    else
  53.       cout<<"NO"<<endl;
  54. }
  55.  
  56. signed main() {
  57.    ios::sync_with_stdio(0);cin.tie(0);
  58. #ifndef ONLINE_JUDGE
  59.    freopen("input.txt", "r", stdin);
  60.    freopen("output.txt", "w", stdout);
  61. #endif
  62.    int t=1;
  63.    cin>>t;
  64.    while(t--)
  65.       solve();
  66.  
  67.    return 0;
  68. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
2
5 5 9 4
5 4 6
4 1 3
1 3 7
3 2 1
2 1 2
8 7 7 2
1 2 1
3 2 3
5 3 3
7 5 2
7 6 4
6 4 5
1 4 2
stdout
copy 
NO
YES
https://ideone.com/kYU4Oi
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!