# HackerEarth Special paths problem solution

In this HackerEarth Special paths problem solution, You are given an undirected connected graph G with N nodes and M edges. Every node has a value A[i] assigned to it.

The value of a simple path between node u and v is as follows:

The maximum absolute difference between the values of adjacent nodes present in the simple path.
Find the minimum possible path value of any simple paths between start and end nodes.

## HackerEarth Special paths problem solution.

`#include<bits/stdc++.h>#define ll long long intusing namespace std;int parent[100000+1];int size[100000+1];int par(int u){    while(u != parent[u])    {        u = parent[u];    }    return u;} void merge(int u, int v){    if(size[u] < size[v])    {        parent[u] = v;        size[v] += size[u];    }    else    {        parent[v] = u;        size[u] += size[v];    }}void solve(){    int n, m;    cin >> n >> m;    assert(1 <= n and n <= 100000);    assert(1 <= m and m <= 100000);    vector<pair<int,int> >edge;    for(int i = 1 ; i <= m ; i++)    {        int u, v;        cin >> u >> v;        assert(u != v);        assert(1 <= u and u <= n);        assert(1 <= v and v <= n);        edge.push_back(make_pair(u,v));    }    int value[n+1];    for(int i = 1 ; i <= n ; i++){        cin >> value[i];        assert(1 <= value[i] and value[i] <= 1000000);    }    int start, end;    cin >> start >> end;    int s = 1;    int e = 1000000;    int ans = -1;    while(s <= e)    {        int mid = (s + e) >> 1;        for(int i = 1 ; i <= n ; i++)        {            parent[i] = i;            size[i] = 1;        }        for(int i = 0 ; i < m ; i++)        {            int u = edge[i].first;            int v = edge[i].second;            int pu = par(u);            int pv = par(v);            int val = abs(value[u] - value[v]);            if(val > mid) continue;             if(pu != pv){                merge(pu,pv);            }        }        if(par(start) == par(end))        {            ans = mid;            e = mid - 1;        }        else        {            s = mid + 1;        }    }    cout << ans << endl;}int main(){    int t = 1;    while(t--)    {        solve();    }}`

### Second solution

`#include <bits/stdc++.h>using namespace std;const int maxn = 1e5 + 14;struct Dsu{    int par[maxn];    Dsu(){  memset(par, -1, sizeof par);  }    int root(int v){        return par[v] < 0 ? v : par[v] = root(par[v]);    }    bool fri(int v, int u){        return root(v) == root(u);    }    bool merge(int v, int u){        if((v = root(v)) == (u = root(u)))            return 0;        par[u] += par[v];        par[v] = u;        return 1;    }}  dsu;int n, m, v[maxn], u[maxn], a[maxn];int main() {    ios::sync_with_stdio(0), cin.tie(0);    cin >> n >> m;    for (int i = 0; i < m; ++i) {        cin >> v[i] >> u[i];        v[i]--, u[i]--;    }    for (int i = 0; i < n; ++i) {        cin >> a[i];    }    int s, e;    cin >> s >> e;    s--, e--;    int lo = -1, hi = 1e6;    while(hi - lo > 1){        dsu = Dsu();        int mid = (lo + hi) / 2;        for (int i = 0; i < m; ++i) {            if(abs(a[v[i]] - a[u[i]]) <= mid)                dsu.merge(v[i], u[i]);        }        (dsu.fri(s, e) ? hi : lo) = mid;    }    cout << hi << '\n';}`