Stucked on the question asked in Google test

Please Help with explained code stuck for 2 days.

For every edge (u,v) in the set of edges assign a weight of |A_u-A_v| to it. After that perform a binary search over the edge weights where for any x we ask the following question.

  • Is it possible to reach node E from S by only passing through edges that have a
    weight less than x ?

We can easily check it linear time with a bfs. So the Final time complexity of the solution would be \mathcal{O}((N+M )\log A_i)

#include "bits/stdc++.h"
#define ar array  
using namespace std ;
const int mxN=1e5 ;
int n,m,s,e,a[mxN+1] ;
vector<ar<int,2>>adj[mxN+1] ;
int main(){
  cin>>n>>m >>s  >> e ,--s,--e ;
  for(int i=0;i<n;i++)
    cin >>a[i] ;
  for(int i=0,u,v;i<m;i++){
    cin>>u>>v;--u,--v ;
    int w = abs(a[u]-a[v]) ;
    adj[u].push_back({v,w}) ;
    adj[v].push_back({u,w}) ;
  auto ok=[&](int x){
    vector<int>di(n,-1) ;
    queue<int>qu ;
    di[s]=0 ;qu.push(s) ;
      int u=qu.front() ;
      qu.pop() ;
          continue  ;
        qu.push(v[0]) ;
        di[v[0]]=di[u]+1 ;
    return (di[e]!=-1) ;
  } ;
  int lb=0,rb=1e9 ;
    int mb=(lb+rb)/2;
    ok(mb)==0?lb=mb+1:rb=mb  ;
  cout << lb << '\n' ;

1 Like