Paste Search Dynamic
Recent pastes
ans
  1. //nani?
  2. #include<bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp> // Common file
  4. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  5.  
  6. //#define pi acos(-1);
  7. #define fs first
  8. #define sc second
  9. #define pb push_back
  10. #define mp make_pair
  11. #define f(i,a,b) for( int i = a; i < b ; i++ )
  12. #define sor(a) sort( a.begin(), a.end() )
  13. #define rsor(a) sort( a.rbegin(), a.rend() )
  14. #define fastio ios_base::sync_with_stdio(0);cin.tie(0)
  15. typedef long long ll;
  16. typedef long double ld;
  17. using namespace std;
  18. using namespace __gnu_pbds;
  19. const ll inf=1e18+7;
  20. const ll INF = 1e18+7;
  21. const ll MOD=1e9+7;
  22. const ll mod=1e9+7;
  23. // ac cmtr;
  24. const int MX = 2e6 +5;
  25. const int LG = 25;
  26. //const int INF = int(1e9);
  27. //const li INF64 = li(1e18);
  28.  
  29. typedef tree<
  30. pair <ll,ll>,
  31. null_type,
  32. less<pair <ll,ll>>,
  33. rb_tree_tag,
  34. tree_order_statistics_node_update>
  35. ordered_set;
  36.  
  37. #define trace(...) fff(#__VA_ARGS__, __VA_ARGS__)
  38. template<typename t> void fff(const char* x, t&& val1) { cout<<x<< " : "<<val1<<"n";}
  39. template<typename t1, typename... t2> void fff(const char* x, t1&& val1, t2&&... val2){
  40.     const char* xd=strchr(x+1, ',');
  41.     cout.write(x, xd-x)<<" : "<<val1<<" | ";
  42.     fff(xd+1, val2...);
  43. }
  44. //---------------------------
  45. struct edge{
  46.     ll a,b,w;  
  47. };
  48. vector <pair <ll,ll> > adj[MX],adj1[MX];
  49. ll n;
  50. ll dp[MX],dp1[MX];
  51. void dij(ll a){
  52.     set <pair <ll,ll> > s;
  53.     f(i,0,n+5) {dp[i]=inf;}
  54.     s.insert(mp(0,a));
  55.     dp[a] = 0;
  56.     while(!s.empty()){
  57.         ll ini  = s.begin()->sc;s.erase(s.begin());
  58.         for(auto xd : adj[ini]){
  59.             if(dp[xd.fs] > dp[ini] + xd.sc){
  60.                 s.erase(mp(dp[xd.fs],xd.fs));
  61.                 dp[xd.fs] = dp[ini] + xd.sc;
  62.                 s.insert(mp(dp[xd.fs],xd.fs));
  63.             }
  64.         }
  65.  
  66.     }
  67.   return;
  68. }
  69. void dij1(ll a){
  70.     set <pair <ll,ll> > s;
  71.     f(i,0,n+5) {dp1[i]=inf;}
  72.     s.insert(mp(0,a));
  73.     dp1[a] = 0;
  74.     while(!s.empty()){
  75.         ll ini  = s.begin()->sc;s.erase(s.begin());
  76.         for(auto xd : adj1[ini]){
  77.             if(dp1[xd.fs] > dp1[ini] + xd.sc){
  78.                 s.erase(mp(dp1[xd.fs],xd.fs));
  79.                 dp1[xd.fs] = dp1[ini] + xd.sc;
  80.                 s.insert(mp(dp1[xd.fs],xd.fs));
  81.             }
  82.         }
  83.  
  84.     }
  85.   return;
  86. }
  87. int main() {
  88.     fastio;
  89.     ll tc; cin >> tc;
  90.     while(tc--){
  91.         ll m,s,t,p; cin >> n >> m >> s >> t >> p;
  92.         vector <edge> e;
  93.         f(i,0,n+5){
  94.             dp[i] = dp1[i] = 0 ;
  95.             adj[i].clear();adj1[i].clear();
  96.         }
  97.         f(i,0,m){
  98.             ll x,y,w; cin >> x >> y >> w;
  99.             adj[x].pb({y,w});
  100.             adj1[y].pb({x,w});
  101.             e.pb({x,y,w});
  102.             //e.pb({y,x,w});
  103.         }  
  104.         dij(s);dij1(t);
  105.         ll ans = -1;
  106.         f(i,0,e.size()){
  107.             ll rep = dp[e[i].a] + e[i].w + dp1[e[i].b];
  108.             if(rep <= p) ans = max(ans,e[i].w);
  109.             ans = min(ans,rep);
  110.         }
  111.         cout << ans << endl;
  112.     }
  113.  
  114.  
  115.  
  116. }
  117.  
Parsed in 0.011 seconds