Shortest path query

#include <bits/stdc++.h>

#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 5e4 + 5;

int n, m, q;
vector<pii> adj[MAXN], hull[MAXN];

bool ccw(pii a, pii b, pii c){
    return (ll)a.X * (b.Y - c.Y) + (ll)b.X * (c.Y - a.Y) + (ll)c.X * (a.Y - b.Y) > 0LL;
}

void gethull(int node){
    if(!hull[node].empty()) return;

    if(node == 1){
        hull[1].push_back({0, 0});
        return;
    }

    vector<pii> temp;
    for(auto &nxt : adj[node]){
        gethull(nxt.X);

        for(auto &e : hull[nxt.X]){
            if(nxt.Y == 0) temp.push_back({e.X + 1, e.Y});
            else temp.push_back({e.X, e.Y + 1});
        }
    }

    sort(temp.begin(), temp.end());

    for(auto &point : temp){
        while(hull[node].size() >= 2 &&
              !ccw(hull[node][hull[node].size() - 2], hull[node][hull[node].size() - 1], point))
                hull[node].pop_back();

        hull[node].push_back(point);
    }
}

int dist(int a, int b, pii point){
    return a * point.X + b * point.Y;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;

        adj[b].push_back({a, c});
    }

    cin >> q;
    while(q--){
        int a, b, x;
        cin >> a >> b >> x;

        gethull(x);

        int l = 0, r = hull[x].size() - 1;
        while(r > l){
            int m = (l + r) / 2;

            if(dist(a, b, hull[x][m]) <= dist(a, b, hull[x][m + 1])) r = m;
            else l = m + 1;
        }

        cout << dist(a, b, hull[x][l]) << '\n';
    }

    return 0;
}