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 deque
using 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});
}
}
}

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

int q;
cin >> q;
FOR(i,q){
int u,l,r,k;
cin >> u >> l >> r >> k;
u--;l--;r--;
}
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}```