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;
}