HackerEarth Minimum Valid Path problem solution YASH PAL, 31 July 2024 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: For any two adjacent edges x and y on the path, 0.5*weight(x) <= weight(y) <= 2*weight(x) 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;} coding problems