# HackerEarth Weird Graph Query problem solution

In this HackerEarth Weird Graph Query problem solution, We are given a connected undirected weighted graph of N nodes and M edges. We are then given Q queries wherein each query we are given integers U, L, R, K. For every query we have to report the smallest integer C such that there are at least K nodes x such that L <= x <= R and the shortest distance from x to U is not more than C.

## HackerEarth Weird Graph Query problem solution.

`#include <iostream>#include <vector>#include <algorithm>#include <fstream>#include <queue>#include <deque>#include <iomanip>#include <cmath>#include <set>#include <stack>#include <map>#include <unordered_map>#define FOR(i,n) for(int i=0;i<n;i++)#define FORE(i,a,b) for(int i=a;i<=b;i++)#define ll long long //#define int long long#define ld long double#define vi deque<int>#define pb push_back#define ff first#define ss second#define ii pair<int,int>#define iii pair<int,ii>#define il pair<int,ll>#define li pair<ll,int>#define pll pair<ll,ll>#define _path pair<ll,pair<ll,int> > #define vv dequeusing namespace std;const int MAXN = 1000+5;const int INF = 1e9;struct Node{    int left;    int right;    int data;    Node(){        left = -1;        right = -1;        data = 0;    }};Node buf[2000*1000*10];int PTR;int get(){    return PTR++;}int get(int a,int b,int c){    buf[PTR].left = a;    buf[PTR].right = b;    buf[PTR].data = c;    return PTR++;}inline void expand(int node){    if(buf[node].left == -1)buf[node].left = get();    if(buf[node].right == -1)buf[node].right = get();}int update(int node,int ss,int se,int i,int val){    if(i < ss or i > se)return node;    if(ss == se){        return get(-1,-1,val);    }    expand(node);        int mid = (ss+se)/2;    int x = update(buf[node].left,ss,mid,i,val);    int y = update(buf[node].right,mid+1,se,i,val);    return get(x,y,buf[x].data + buf[y].data);}int get(int node,int ss,int se,int l,int r){    if(r < ss or l > se or node == -1)return 0;    if(l <= ss and se <= r)return buf[node].data;    int mid = (ss+se)/2;    return get(buf[node].left,ss,mid,l,r) + get(buf[node].right,mid+1,se,l,r);}vv<ii> g[MAXN];int dist[MAXN][MAXN];vv<ii> allversions[MAXN];void dijkstra(int source,int n){    priority_queue<ii,vv<ii>,greater<ii> > pq;    FOR(i,n)dist[source][i] = INF;    pq.push({0,source});    while(!pq.empty()){        auto item = pq.top();pq.pop();        if(dist[source][item.ss] <= item.ff)continue;        dist[source][item.ss] = item.ff;        for(auto e: g[item.ss]){            if(item.ss+e.ss >= dist[source][e.ff])continue;            pq.push({item.ff + e.ss,e.ff});        }    }}void buildPersSegtree(int x,int n){    map<int,vi> all;    FOR(i,n)all[dist[x][i]].pb(i);         allversions[x].pb({0,get()});        for(auto e: all){        int id = allversions[x].back().ss;        for(auto f: e.ss){            id = update(id,0,MAXN,f,1);        }        allversions[x].pb({e.ff,id});    }}bool checkAnswer(int nodeU,int l,int r,int id,int k){    return get(allversions[nodeU][id].ss,0,MAXN,l,r) >= k; }int getAnswer(int node,int l,int r,int k){    int low = 0;    int high = allversions[node].size();    high--;    int best = allversions[node].back().ff;    while(low <= high){        int mid = (low + high)/2;        if(checkAnswer(node,l,r,mid,k)){            best = min(best,allversions[node][mid].ff);            high = mid -1;        }else{            low = mid+1;        }    }    return best;}void solve(){    int n,m;    cin >> n >> m;    FOR(i,m){        int a,b,c;        cin >> a >> b >> c;        a--;b--;        g[a].pb({b,c});        g[b].pb({a,c});    }    FOR(i,n)dijkstra(i,n);    FOR(i,n)buildPersSegtree(i,n);    int q;    cin >> q;    FOR(i,q){        int u,l,r,k;        cin >> u >> l >> r >> k;        u--;l--;r--;        cout << getAnswer(u,l,r,k) << endl;    }}int main(){    ios_base::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);        int t = 1;    // cin >> t;    while(t--){        solve();    }    return 0;}`