# HackerEarth Minimum Valid Path problem solution

In this HackerEarth Minimum valid path problem solution, You are given a weighted directed graph some of whose vertices are marked as special vertices. A valid path in it is a path which satisfies the following conditions:
1. For any two adjacent edges x and y on the path, 0.5*weight(x) <= weight(y) <= 2*weight(x)
2. The path contains exactly one special vertex.

Given two vertices x and y, your task is to calculate the minimum cost of a valid path between them.

## HackerEarth Minimum Valid Path problem solution.

`#include<bits/stdc++.h>using namespace std;#define TRACE#ifdef TRACE#define tr(...) __f(#__VA_ARGS__, __VA_ARGS__)template <typename Arg1>void __f(const char* name, Arg1&& arg1){    cerr << name << " : " << arg1 << std::endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}#else#define tr(...)#endif#define ll long long#define PB push_back#define MP make_pair#define F first#define S second#define SZ(a) (ll)(a.size())#define all(a) a.begin(), a.end() #define fr(i,n) for(i=1;i<=n;i++)#define rp(i,n) for(i=0;i<n;i++)typedef pair<ll, ll> ii;typedef vector<ll> vl;typedef vector<ii> vii;const ll N = 100010;ll a[N];multiset<ii> ms[2][N];multiset<ll> ms1;vii v[2][N];void dij(ll s, ll t, ll f){    if(a[s]==1)    {        v[f][s].PB(MP(0,0));            return;    }    multiset<pair<ll, ii> > dms;    auto it = ms[f][s].begin();    while(it!=ms[f][s].end())    {        dms.insert(MP(it->F, MP(it->F, it->S)));        it=ms[f][s].erase(it);    }    ll cst,nod,wt;    while(!dms.empty())    {        cst=(*(dms.begin())).F;        wt=(*(dms.begin())).S.F;        nod=(*(dms.begin())).S.S;        dms.erase(dms.begin());        if(a[nod]==1)        {            v[f][nod].PB(MP(wt,cst));            continue;        }        it=ms[f][nod].lower_bound(MP((wt+1)/2, -1));        while((it!=ms[f][nod].end()) && ((it->F)<=2*wt))        {            dms.insert(MP(cst+it->F, MP(it->F, it->S)));            it=ms[f][nod].erase(it);        }    }    return;}int main(){    ll n,m,x,y,z,i,k,s,t,mn=1e18,j,tp;    cin>>n>>m;    fr(i,m)    {        cin>>x>>y>>z;        ms[0][x].insert(MP(z,y));        ms[1][y].insert(MP(z,x));    }    cin>>k;    fr(i,k) cin>>x, a[x]=1;    cin>>s>>t;    if(s==t)    {        if(a[s]==1)            cout<<0<<endl;        else            cout<<-1<<endl;        return 0;    }    else if(a[s]==1 && a[t]==1)    {        cout<<-1<<endl;        return 0;    }    dij(s,t,0);    dij(t,s,1);    fr(i,n) if((!v[0][i].empty()) && (!v[1][i].empty()))    {//        tr(i,SZ(v[0][i]),SZ(v[1][i]));        if(v[0][i][0].F==0 && v[0][i][0].S==0)            rp(j,SZ(v[1][i])) mn=min(mn, v[1][i][j].S);         else if(v[1][i][0].F==0 && v[1][i][0].S==0)            rp(j,SZ(v[0][i])) mn=min(mn, v[0][i][j].S);        else        {            ms1.clear();            sort(all(v[0][i])), sort(all(v[1][i]));            x=0, y=0;            rp(x,SZ(v[0][i]))            {                tp=v[0][i][x].F;                while(y<SZ(v[1][i]) && v[1][i][y].F<=2*tp) ms1.insert(v[1][i][y++].S);                while((!ms1.empty()) && tp>2*(*(ms1.begin()))) ms1.erase(ms1.begin());                if(!ms1.empty()) mn=min(mn, v[0][i][x].S+(*(ms1.begin())));             }        }    }    if(mn==1e18)        cout<<-1<<endl;    else        cout<<mn<<endl;    return 0;}`