#include "walk.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
vector<vector<int>> adj;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r,
vector<int> y, int s, int g) {
map<int, vector<int>> bridge_by_y;
for (int i = 0; i < y.size(); i++) {
if (!bridge_by_y.count(y[i]))
bridge_by_y[y[i]] = vector<int>();
bridge_by_y[y[i]].push_back(i);
}
priority_queue<tuple<ll, ll, ll>> que;
que.push({0, s, 0});
map<pair<ll, ll>, ll> dists;
while (que.size()) {
auto [dist, building, height] = que.top();
que.pop();
dist *= -1;
if (dists.count({building, height}) && dists[{building, height}] < dist)
continue;
for (int i = 0; i < l.size(); i++)
if (l[i] <= building && building <= r[i] && y[i] <= h[building]) {
ll new_dist = dist + abs(height - y[i]);
if (!dists.count({building, y[i]}) ||
new_dist < dists[{building, y[i]}]) {
dists[{building, y[i]}] = new_dist;
que.push({-new_dist, building, y[i]});
}
}
if (!bridge_by_y.count(height))
continue;
for (int bridge : bridge_by_y[height]) {
if (!(l[bridge] <= building && building <= r[bridge]))
continue;
for (int build = l[bridge]; build <= r[bridge]; build++) {
if (y[bridge] > h[build])
continue;
ll new_dist = dist + abs(x[build] - x[building]);
if (!dists.count({build, height}) ||
new_dist < dists[{build, height}]) {
dists[{build, height}] = new_dist;
que.push({-new_dist, build, height});
}
}
}
}
ll ans = -1;
for (auto [key, dist] : dists) {
auto [building, height] = key;
if (building == g)
if (ans == -1 || dist + height < ans)
ans = dist + height;
}
return ans;
}
