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


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