IOI 2019 - Sky Walking
Buildings are vertical segments, skywalks are horizontal segments, and movement is allowed only along those segments. We want the shortest path from the bottom of building s to the bottom of building g.
IOI2019TeXC++
Source of truth
Source-first archive entry
This page is built from the copied files in competitive_programming/ioi/2019/walk. Edit
competitive_programming/ioi/2019/walk/solution.tex to update the written solution and
competitive_programming/ioi/2019/walk/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem statement
Problem Statement
Rendered from the "Problem Summary" section inside solution.tex because this entry has no separate statement file.
Buildings are vertical segments, skywalks are horizontal segments, and movement is allowed only along those segments. We want the shortest path from the bottom of building $s$ to the bottom of building $g$.
Editorial
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Official Geometric Pruning
The official review proves two key facts.
For the general case, every skywalk crossing $s$ or $g$ can be split at the nearest tall buildings around that special building. After this preprocessing, the shortest path length is unchanged.
In the resulting instance, every relevant vertical move ends at a skywalk endpoint. Therefore only $O(M)$ vertical edges remain relevant.
Step 1: Split Skywalks Around $s$ and $g$
For a skywalk $(l,r,y)$ with $l < s < r$, let \[ a = \max\{\,i \in [l,s] : h_i \ge y\,\}, \qquad b = \min\{\,i \in [s,r] : h_i \ge y\,\}. \] Replace $(l,r,y)$ by up to three skywalks: \[ (l,a,y),\ (a,b,y),\ (b,r,y), \] discarding zero-length pieces. Do the same for $g$. The indices $a$ and $b$ are found with a segment tree over building heights.
Step 2: Relevant Vertical Edges
Process skywalks in increasing height. Maintain, for each building, the height of the highest already-processed skywalk that crosses it. This is a range-assignment / point-query structure.
For an endpoint $(i,y)$ of a skywalk:
the lower endpoint of its relevant vertical edge is the previous crossing height on building $i$, if one exists;
otherwise it is height $0$ only when $i \in \{s,g\}$.
So every skywalk endpoint contributes at most one vertical edge, hence only $O(M)$ relevant vertical edges exist.
Step 3: Relevant Horizontal Nodes
A point $(i,y)$ is kept in the graph if it is:
a skywalk endpoint,
the lower endpoint of a relevant vertical edge, or
one of the two bottom nodes $(s,0)$ and $(g,0)$.
For each height $y$, skywalk intervals of height $y$ are disjoint except possibly at endpoints. Hence each kept point belongs to at most two skywalks of that height, so we can attach it to the correct skywalk(s) by binary search. Along one skywalk, connect consecutive kept points with horizontal edges.
Final Graph
The graph has only $O(M)$ nodes and edges:
one edge for each relevant vertical segment,
one edge between consecutive kept points on each skywalk.
Run Dijkstra from $(s,0)$ to $(g,0)$.
Complexity
Time: $O(M \log M + M \log N)$.
Space: $O(M)$.
Implementation
// 1. Split skywalks around s and g.
// 2. Sweep heights upward and generate all relevant vertical edges.
// 3. Collect all kept points.
// 4. For each skywalk, connect consecutive kept points horizontally.
// 5. Run Dijkstra on the pruned graph. Source code
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct MaxTree {
int n;
vector<int> mx;
explicit MaxTree(const vector<int> &h) {
n = (int)h.size();
mx.assign(4 * n, 0);
build(1, 0, n - 1, h);
}
void build(int node, int l, int r, const vector<int> &h) {
if (l == r) {
mx[node] = h[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, h);
build(node * 2 + 1, mid + 1, r, h);
mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
}
int find_rightmost(int node, int l, int r, int ql, int qr, int need) const {
if (qr < l || r < ql || mx[node] < need) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
int right = find_rightmost(node * 2 + 1, mid + 1, r, ql, qr, need);
if (right != -1) return right;
return find_rightmost(node * 2, l, mid, ql, qr, need);
}
int find_leftmost(int node, int l, int r, int ql, int qr, int need) const {
if (qr < l || r < ql || mx[node] < need) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
int left = find_leftmost(node * 2, l, mid, ql, qr, need);
if (left != -1) return left;
return find_leftmost(node * 2 + 1, mid + 1, r, ql, qr, need);
}
};
struct AssignTree {
int n;
vector<int> lazy;
explicit AssignTree(int n_) : n(n_), lazy(4 * n_, -1) {}
void assign_range(int node, int l, int r, int ql, int qr, int val) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[node] = val;
return;
}
int mid = (l + r) / 2;
if (lazy[node] != -1) {
lazy[node * 2] = lazy[node];
lazy[node * 2 + 1] = lazy[node];
lazy[node] = -1;
}
assign_range(node * 2, l, mid, ql, qr, val);
assign_range(node * 2 + 1, mid + 1, r, ql, qr, val);
}
int point_query(int node, int l, int r, int pos) const {
if (l == r || lazy[node] != -1) return max(lazy[node], 0);
int mid = (l + r) / 2;
if (pos <= mid) return point_query(node * 2, l, mid, pos);
return point_query(node * 2 + 1, mid + 1, r, pos);
}
};
struct Skywalk {
int l, r, y;
};
struct VerticalEdge {
int building;
int low;
int high;
};
long long min_distance(vector<int> x, vector<int> h,
vector<int> l, vector<int> r, vector<int> y,
int s, int g) {
if (s == g) return 0;
int n = (int)x.size();
vector<Skywalk> walks;
walks.reserve(l.size() * 5);
for (int i = 0; i < (int)l.size(); ++i) walks.push_back({l[i], r[i], y[i]});
MaxTree tall(h);
auto split_at = [&](int pivot) {
vector<Skywalk> next;
next.reserve(walks.size() * 3);
for (const Skywalk &sw : walks) {
if (!(sw.l < pivot && pivot < sw.r)) {
next.push_back(sw);
continue;
}
int left = tall.find_rightmost(1, 0, n - 1, sw.l, pivot, sw.y);
int right = tall.find_leftmost(1, 0, n - 1, pivot, sw.r, sw.y);
if (sw.l < left) next.push_back({sw.l, left, sw.y});
if (left < right) next.push_back({left, right, sw.y});
if (right < sw.r) next.push_back({right, sw.r, sw.y});
}
walks.swap(next);
};
split_at(s);
if (g != s) split_at(g);
vector<int> order(walks.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (walks[a].y != walks[b].y) return walks[a].y < walks[b].y;
if (walks[a].l != walks[b].l) return walks[a].l < walks[b].l;
return walks[a].r < walks[b].r;
});
vector<vector<int>> sky_nodes(walks.size());
vector<pair<int, int>> points;
points.reserve(walks.size() * 6 + 4);
vector<VerticalEdge> verticals;
verticals.reserve(walks.size() * 4);
auto add_point = [&](int building, int ht) {
points.push_back({building, ht});
};
add_point(s, 0);
add_point(g, 0);
AssignTree cover(n);
for (int i = 0; i < (int)order.size();) {
int j = i;
while (j < (int)order.size() && walks[order[i]].y == walks[order[j]].y) ++j;
for (int k = i; k < j; ++k) {
int id = order[k];
const Skywalk &sw = walks[id];
add_point(sw.l, sw.y);
add_point(sw.r, sw.y);
int pred_l = cover.point_query(1, 0, n - 1, sw.l);
if (pred_l > 0 || sw.l == s || sw.l == g) {
int low = pred_l > 0 ? pred_l : 0;
add_point(sw.l, low);
verticals.push_back({sw.l, low, sw.y});
}
int pred_r = cover.point_query(1, 0, n - 1, sw.r);
if (pred_r > 0 || sw.r == s || sw.r == g) {
int low = pred_r > 0 ? pred_r : 0;
add_point(sw.r, low);
verticals.push_back({sw.r, low, sw.y});
}
}
for (int k = i; k < j; ++k) {
int id = order[k];
cover.assign_range(1, 0, n - 1, walks[id].l, walks[id].r, walks[id].y);
}
i = j;
}
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
unordered_map<long long, int> node_id;
node_id.reserve(points.size() * 2 + 8);
for (int i = 0; i < (int)points.size(); ++i) {
long long key = (static_cast<long long>(points[i].first) << 32) ^
static_cast<unsigned int>(points[i].second);
node_id[key] = i;
}
vector<vector<pair<int, ll>>> adj(points.size());
auto add_edge = [&](int u, int v, ll wgt) {
adj[u].push_back({v, wgt});
adj[v].push_back({u, wgt});
};
for (const VerticalEdge &ve : verticals) {
long long key_low = (static_cast<long long>(ve.building) << 32) ^
static_cast<unsigned int>(ve.low);
long long key_high = (static_cast<long long>(ve.building) << 32) ^
static_cast<unsigned int>(ve.high);
add_edge(node_id[key_low], node_id[key_high], ve.high - ve.low);
}
unordered_map<int, vector<pair<pair<int, int>, int>>> by_height;
by_height.reserve(walks.size() * 2 + 1);
for (int i = 0; i < (int)walks.size(); ++i) {
by_height[walks[i].y].push_back({{walks[i].l, walks[i].r}, i});
}
for (auto &entry : by_height) {
auto &vec = entry.second;
sort(vec.begin(), vec.end());
}
for (const auto &[building, ht] : points) {
if (ht == 0) continue;
auto it = by_height.find(ht);
if (it == by_height.end()) continue;
const auto &vec = it->second;
int pos = lower_bound(
vec.begin(), vec.end(),
make_pair(make_pair(building + 1, numeric_limits<int>::min()), numeric_limits<int>::min())) -
vec.begin();
auto attach = [&](int idx) {
if (idx < 0 || idx >= (int)vec.size()) return;
int id = vec[idx].second;
const Skywalk &sw = walks[id];
if (sw.l <= building && building <= sw.r) sky_nodes[id].push_back(building);
};
attach(pos - 1);
attach(pos - 2);
}
for (int i = 0; i < (int)walks.size(); ++i) {
auto &vec = sky_nodes[i];
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int j = 0; j + 1 < (int)vec.size(); ++j) {
int a = vec[j];
int b = vec[j + 1];
long long key_a = (static_cast<long long>(a) << 32) ^
static_cast<unsigned int>(walks[i].y);
long long key_b = (static_cast<long long>(b) << 32) ^
static_cast<unsigned int>(walks[i].y);
add_edge(node_id[key_a], node_id[key_b], (ll)x[b] - x[a]);
}
}
long long src_key = (static_cast<long long>(s) << 32);
long long dst_key = (static_cast<long long>(g) << 32);
int src = node_id[src_key];
int dst = node_id[dst_key];
const ll INF = (1LL << 62);
vector<ll> dist(points.size(), INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
if (u == dst) return d;
for (auto [v, wgt] : adj[u]) {
if (d + wgt < dist[v]) {
dist[v] = d + wgt;
pq.push({dist[v], v});
}
}
}
return -1;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<int> x(n), h(n);
for (int i = 0; i < n; ++i) scanf("%d %d", &x[i], &h[i]);
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; ++i) scanf("%d %d %d", &l[i], &r[i], &y[i]);
int s, g;
scanf("%d %d", &s, &g);
printf("%lld\n", min_distance(x, h, l, r, y, s, g));
return 0;
}
Source files
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{xcolor}
\lstset{
language=C++,
basicstyle=\ttfamily\small,
keywordstyle=\color{blue}\bfseries,
commentstyle=\color{gray},
numbers=left,
numberstyle=\tiny\color{gray},
breaklines=true,
frame=single,
tabsize=4,
showstringspaces=false
}
\title{IOI 2019 -- Sky Walking}
\author{Solution}
\date{}
\begin{document}
\maketitle
\section{Problem Summary}
Buildings are vertical segments, skywalks are horizontal segments, and movement is allowed only
along those segments.
We want the shortest path from the bottom of building $s$ to the bottom of building $g$.
\section{Official Geometric Pruning}
The official review proves two key facts.
\begin{enumerate}
\item For the general case, every skywalk crossing $s$ or $g$ can be split at the nearest tall
buildings around that special building. After this preprocessing, the shortest path length is
unchanged.
\item In the resulting instance, every relevant vertical move ends at a \emph{skywalk endpoint}.
Therefore only $O(M)$ vertical edges remain relevant.
\end{enumerate}
\section{Step 1: Split Skywalks Around $s$ and $g$}
For a skywalk $(l,r,y)$ with $l < s < r$, let
\[
a = \max\{\,i \in [l,s] : h_i \ge y\,\}, \qquad
b = \min\{\,i \in [s,r] : h_i \ge y\,\}.
\]
Replace $(l,r,y)$ by up to three skywalks:
\[
(l,a,y),\ (a,b,y),\ (b,r,y),
\]
discarding zero-length pieces.
Do the same for $g$.
The indices $a$ and $b$ are found with a segment tree over building heights.
\section{Step 2: Relevant Vertical Edges}
Process skywalks in increasing height.
Maintain, for each building, the height of the highest already-processed skywalk that crosses it.
This is a range-assignment / point-query structure.
For an endpoint $(i,y)$ of a skywalk:
\begin{itemize}
\item the lower endpoint of its relevant vertical edge is the previous crossing height on
building $i$, if one exists;
\item otherwise it is height $0$ only when $i \in \{s,g\}$.
\end{itemize}
So every skywalk endpoint contributes at most one vertical edge, hence only $O(M)$ relevant
vertical edges exist.
\section{Step 3: Relevant Horizontal Nodes}
A point $(i,y)$ is kept in the graph if it is:
\begin{itemize}
\item a skywalk endpoint,
\item the lower endpoint of a relevant vertical edge, or
\item one of the two bottom nodes $(s,0)$ and $(g,0)$.
\end{itemize}
For each height $y$, skywalk intervals of height $y$ are disjoint except possibly at endpoints.
Hence each kept point belongs to at most two skywalks of that height, so we can attach it to the
correct skywalk(s) by binary search.
Along one skywalk, connect consecutive kept points with horizontal edges.
\section{Final Graph}
The graph has only $O(M)$ nodes and edges:
\begin{itemize}
\item one edge for each relevant vertical segment,
\item one edge between consecutive kept points on each skywalk.
\end{itemize}
Run Dijkstra from $(s,0)$ to $(g,0)$.
\section{Complexity}
\begin{itemize}
\item \textbf{Time:} $O(M \log M + M \log N)$.
\item \textbf{Space:} $O(M)$.
\end{itemize}
\section{Implementation}
\begin{lstlisting}
// 1. Split skywalks around s and g.
// 2. Sweep heights upward and generate all relevant vertical edges.
// 3. Collect all kept points.
// 4. For each skywalk, connect consecutive kept points horizontally.
// 5. Run Dijkstra on the pruned graph.
\end{lstlisting}
\end{document}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct MaxTree {
int n;
vector<int> mx;
explicit MaxTree(const vector<int> &h) {
n = (int)h.size();
mx.assign(4 * n, 0);
build(1, 0, n - 1, h);
}
void build(int node, int l, int r, const vector<int> &h) {
if (l == r) {
mx[node] = h[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, h);
build(node * 2 + 1, mid + 1, r, h);
mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
}
int find_rightmost(int node, int l, int r, int ql, int qr, int need) const {
if (qr < l || r < ql || mx[node] < need) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
int right = find_rightmost(node * 2 + 1, mid + 1, r, ql, qr, need);
if (right != -1) return right;
return find_rightmost(node * 2, l, mid, ql, qr, need);
}
int find_leftmost(int node, int l, int r, int ql, int qr, int need) const {
if (qr < l || r < ql || mx[node] < need) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
int left = find_leftmost(node * 2, l, mid, ql, qr, need);
if (left != -1) return left;
return find_leftmost(node * 2 + 1, mid + 1, r, ql, qr, need);
}
};
struct AssignTree {
int n;
vector<int> lazy;
explicit AssignTree(int n_) : n(n_), lazy(4 * n_, -1) {}
void assign_range(int node, int l, int r, int ql, int qr, int val) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[node] = val;
return;
}
int mid = (l + r) / 2;
if (lazy[node] != -1) {
lazy[node * 2] = lazy[node];
lazy[node * 2 + 1] = lazy[node];
lazy[node] = -1;
}
assign_range(node * 2, l, mid, ql, qr, val);
assign_range(node * 2 + 1, mid + 1, r, ql, qr, val);
}
int point_query(int node, int l, int r, int pos) const {
if (l == r || lazy[node] != -1) return max(lazy[node], 0);
int mid = (l + r) / 2;
if (pos <= mid) return point_query(node * 2, l, mid, pos);
return point_query(node * 2 + 1, mid + 1, r, pos);
}
};
struct Skywalk {
int l, r, y;
};
struct VerticalEdge {
int building;
int low;
int high;
};
long long min_distance(vector<int> x, vector<int> h,
vector<int> l, vector<int> r, vector<int> y,
int s, int g) {
if (s == g) return 0;
int n = (int)x.size();
vector<Skywalk> walks;
walks.reserve(l.size() * 5);
for (int i = 0; i < (int)l.size(); ++i) walks.push_back({l[i], r[i], y[i]});
MaxTree tall(h);
auto split_at = [&](int pivot) {
vector<Skywalk> next;
next.reserve(walks.size() * 3);
for (const Skywalk &sw : walks) {
if (!(sw.l < pivot && pivot < sw.r)) {
next.push_back(sw);
continue;
}
int left = tall.find_rightmost(1, 0, n - 1, sw.l, pivot, sw.y);
int right = tall.find_leftmost(1, 0, n - 1, pivot, sw.r, sw.y);
if (sw.l < left) next.push_back({sw.l, left, sw.y});
if (left < right) next.push_back({left, right, sw.y});
if (right < sw.r) next.push_back({right, sw.r, sw.y});
}
walks.swap(next);
};
split_at(s);
if (g != s) split_at(g);
vector<int> order(walks.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (walks[a].y != walks[b].y) return walks[a].y < walks[b].y;
if (walks[a].l != walks[b].l) return walks[a].l < walks[b].l;
return walks[a].r < walks[b].r;
});
vector<vector<int>> sky_nodes(walks.size());
vector<pair<int, int>> points;
points.reserve(walks.size() * 6 + 4);
vector<VerticalEdge> verticals;
verticals.reserve(walks.size() * 4);
auto add_point = [&](int building, int ht) {
points.push_back({building, ht});
};
add_point(s, 0);
add_point(g, 0);
AssignTree cover(n);
for (int i = 0; i < (int)order.size();) {
int j = i;
while (j < (int)order.size() && walks[order[i]].y == walks[order[j]].y) ++j;
for (int k = i; k < j; ++k) {
int id = order[k];
const Skywalk &sw = walks[id];
add_point(sw.l, sw.y);
add_point(sw.r, sw.y);
int pred_l = cover.point_query(1, 0, n - 1, sw.l);
if (pred_l > 0 || sw.l == s || sw.l == g) {
int low = pred_l > 0 ? pred_l : 0;
add_point(sw.l, low);
verticals.push_back({sw.l, low, sw.y});
}
int pred_r = cover.point_query(1, 0, n - 1, sw.r);
if (pred_r > 0 || sw.r == s || sw.r == g) {
int low = pred_r > 0 ? pred_r : 0;
add_point(sw.r, low);
verticals.push_back({sw.r, low, sw.y});
}
}
for (int k = i; k < j; ++k) {
int id = order[k];
cover.assign_range(1, 0, n - 1, walks[id].l, walks[id].r, walks[id].y);
}
i = j;
}
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
unordered_map<long long, int> node_id;
node_id.reserve(points.size() * 2 + 8);
for (int i = 0; i < (int)points.size(); ++i) {
long long key = (static_cast<long long>(points[i].first) << 32) ^
static_cast<unsigned int>(points[i].second);
node_id[key] = i;
}
vector<vector<pair<int, ll>>> adj(points.size());
auto add_edge = [&](int u, int v, ll wgt) {
adj[u].push_back({v, wgt});
adj[v].push_back({u, wgt});
};
for (const VerticalEdge &ve : verticals) {
long long key_low = (static_cast<long long>(ve.building) << 32) ^
static_cast<unsigned int>(ve.low);
long long key_high = (static_cast<long long>(ve.building) << 32) ^
static_cast<unsigned int>(ve.high);
add_edge(node_id[key_low], node_id[key_high], ve.high - ve.low);
}
unordered_map<int, vector<pair<pair<int, int>, int>>> by_height;
by_height.reserve(walks.size() * 2 + 1);
for (int i = 0; i < (int)walks.size(); ++i) {
by_height[walks[i].y].push_back({{walks[i].l, walks[i].r}, i});
}
for (auto &entry : by_height) {
auto &vec = entry.second;
sort(vec.begin(), vec.end());
}
for (const auto &[building, ht] : points) {
if (ht == 0) continue;
auto it = by_height.find(ht);
if (it == by_height.end()) continue;
const auto &vec = it->second;
int pos = lower_bound(
vec.begin(), vec.end(),
make_pair(make_pair(building + 1, numeric_limits<int>::min()), numeric_limits<int>::min())) -
vec.begin();
auto attach = [&](int idx) {
if (idx < 0 || idx >= (int)vec.size()) return;
int id = vec[idx].second;
const Skywalk &sw = walks[id];
if (sw.l <= building && building <= sw.r) sky_nodes[id].push_back(building);
};
attach(pos - 1);
attach(pos - 2);
}
for (int i = 0; i < (int)walks.size(); ++i) {
auto &vec = sky_nodes[i];
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int j = 0; j + 1 < (int)vec.size(); ++j) {
int a = vec[j];
int b = vec[j + 1];
long long key_a = (static_cast<long long>(a) << 32) ^
static_cast<unsigned int>(walks[i].y);
long long key_b = (static_cast<long long>(b) << 32) ^
static_cast<unsigned int>(walks[i].y);
add_edge(node_id[key_a], node_id[key_b], (ll)x[b] - x[a]);
}
}
long long src_key = (static_cast<long long>(s) << 32);
long long dst_key = (static_cast<long long>(g) << 32);
int src = node_id[src_key];
int dst = node_id[dst_key];
const ll INF = (1LL << 62);
vector<ll> dist(points.size(), INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
if (u == dst) return d;
for (auto [v, wgt] : adj[u]) {
if (d + wgt < dist[v]) {
dist[v] = d + wgt;
pq.push({dist[v], v});
}
}
}
return -1;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<int> x(n), h(n);
for (int i = 0; i < n; ++i) scanf("%d %d", &x[i], &h[i]);
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; ++i) scanf("%d %d %d", &l[i], &r[i], &y[i]);
int s, g;
scanf("%d %d", &s, &g);
printf("%lld\n", min_distance(x, h, l, r, y, s, g));
return 0;
}