/*
Sky Walking
*/
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
typedef long long ll;
const ll INF = 1ll << 60ll;
struct node
{
ll x, y;
ll index;
vector<pair<int, ll>> adj;
};
struct walk
{
int l, r, y;
bool operator<(const walk other) const
{
return y < other.y;
}
};
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G)
{
const int N = X.size();
const int M = L.size();
vector<walk> walks(M);
for (int i = 0; i < M; i++)
walks[i] = {L[i], R[i], Y[i]};
sort(walks.begin(), walks.end());
// Construct adjacency list
vector<node> nodes;
vector<int> top(N);
for (int i = 0; i < N; i++)
{
nodes.push_back({X[i], 0, i, {}});
top[i] = i;
}
for (auto w : walks)
{
int last = -1;
for (int i = w.l; i <= w.r; i++)
{
if (H[i] < w.y) continue;
int index = nodes.size();
node newNode = {X[i], w.y, index, {}};
ll vdist = w.y - nodes[top[i]].y;
nodes[top[i]].adj.push_back({index, vdist});
newNode.adj.push_back({top[i], vdist});
top[i] = index;
if (last != -1)
{
ll hdist = X[i] - nodes[last].x;
newNode.adj.push_back({last, hdist});
nodes[last].adj.push_back({index, hdist});
}
last = index;
nodes.push_back(newNode);
}
}
priority_queue<pair<ll, int>> q;
q.push({0ll, S});
ll sz = nodes.size();
vector<int> visited(sz);
vector<ll> dist(sz, INF);
dist[S] = 0;
while (!q.empty())
{
int s = q.top().second;
q.pop();
if (visited[s]) continue;
visited[s] = 1;
for (auto n : nodes[s].adj)
{
if (visited[n.first]) continue;
if (dist[s] + n.second < dist[n.first])
{
dist[n.first] = dist[s] + n.second;
q.push({-dist[n.first], n.first});
}
}
}
if (dist[G] == INF)
return -1;
return dist[G];
}
