fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define pill pair<int,ll>
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define ff fi.fi
  12. #define fs fi.se
  13. #define sf se.fi
  14. #define ss se.se
  15. #define MASK(x) (((1)<<(x))-1)
  16. #define getbit(x,k) (((x)>>(k))&1)
  17.  
  18. using namespace std;
  19.  
  20. const int maxn=1e5+50,mod=1e9+7;
  21. const ll inf=0x3f3f3f3f3f3f3f3f;
  22.  
  23. int n,m,q,s,t,k;
  24. int d[maxn];
  25. vector<pii>eg[maxn];
  26.  
  27. bool bfs01(int R)
  28. {
  29.     memset(d,0x3f,sizeof d);d[s]=0;
  30.     deque<int>dQ;
  31.     dQ.push_front(s);
  32.     while(dQ.size())
  33.     {
  34.         int u=dQ.front();dQ.pop_front();
  35.         for(pii v:eg[u])
  36.         {
  37.             int c=(v.se>R);
  38.             if(d[u]+c<d[v.fi])
  39.             {
  40.                 d[v.fi]=d[u]+c;
  41.                 if(c==0) dQ.push_front(v.fi);
  42.                 else dQ.push_back(v.fi);
  43.             }
  44.         }
  45.     }
  46.     return d[t]<=k;
  47. }
  48. int main()
  49. {
  50.     fastio
  51.     cin>>n>>m;
  52.     for(int i=1;i<=m;i++)
  53.     {
  54.         int u,v,c;cin>>u>>v>>c;
  55.         eg[u].pb({v,c});eg[v].pb({u,c});
  56.     }
  57.     cin>>q;
  58.     while(q--)
  59.     {
  60.         cin>>s>>t>>k;
  61.         int l=0,r=1e9,mid,ans=0;
  62.         while(l<=r)
  63.         {
  64.             mid=(l+r)/2;
  65.             if(bfs01(mid)) ans=mid,r=mid-1;
  66.             else l=mid+1;
  67.         }
  68.         cout<<ans<<'\n';
  69.     }
  70. }
  71.  
Success #stdin #stdout 0.01s 5956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mk67GO
language:
C++14 (gcc 8.3)
created:
4 days 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!