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)
CODE
#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) ;
while(qu.size()){
int u=qu.front() ;
qu.pop() ;
for(ar<int,2>v:adj[u]){
if(v[1]>x||di[v[0]]!=-1)
continue ;
qu.push(v[0]) ;
di[v[0]]=di[u]+1 ;
}
}
return (di[e]!=-1) ;
} ;
int lb=0,rb=1e9 ;
while(lb<rb){
int mb=(lb+rb)/2;
ok(mb)==0?lb=mb+1:rb=mb ;
}
cout << lb << '\n' ;
}
1 Like