// #include "walk.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef tuple<int, int, int> tiii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int maxN = 10005;
const ll INF = 1e18;
ll djikstra(vvpii & adj, int s, int g) {
int n = sz(adj);
vi dist(n, INF);
priority_queue<pii, vpii, greater<pii>> q;
q.push({ s, 0 });
while (!q.empty()) {
ll v,d;
tie(v,d) = q.top(); q.pop();
if (dist[v] <= d) continue;
dist[v] = d;
for (pii e : adj[v]) {
ll u,dd;
tie(u,dd) = e;
if (dist[u] == INF) q.push({ u, d + dd});
}
}
return (dist[g] == INF) ? -1 : dist[g];
}
ll min_distance(vpii & B, vtiii &S, int s, int g) {
int n = sz(B);
int m = sz(S);
set<pii> bu; // Häuser nach Positions
vpii BnachH(n); // häuser nach Höhe
F0R(i,n) bu.insert({i, i });
F0R(i,n) BnachH[i] = { B[i].second, i };
sort(all(BnachH), [&](pii & a, pii & b) { return a > b; });
sort(all(S), [&](tiii &a, tiii &b) { return get<2>(a) > get<2>(b); }); // Segmente nach Höhe
vector<set<int>> heightsOnBuildings(n);
F0R(i,n) heightsOnBuildings[i].insert(0), heightsOnBuildings[i].insert(B[i].second);
vvi buildingsOnSegment(m);
F0R(i, m) {
tiii seg = S[i];
int l, r, y;
tie(l, r, y) = seg;
while (BnachH.back().first < y) {
int idx = BnachH.back().second;
bu.erase({ B[idx].first, idx } );
BnachH.pop_back();
}
for (auto it = bu.lower_bound({l, -1}); it != bu.end() && it->first <= r; ++it) {
int idx = it->second;
heightsOnBuildings[idx].insert(y);
buildingsOnSegment[i].push_back(idx);
}
}
vvpii adj;
map<pii, int> nodes;
int idx = 0;
F0R(i,n) {
int last = -1, lastH = -1;
for (int y : heightsOnBuildings[i]) {
nodes[{i, y}] = idx;
adj.push_back(vpii());
if (last != -1) {
adj[last].push_back({ idx, abs(y - lastH) });
adj[idx].push_back({ last, abs(y - lastH) });
}
last = idx;
lastH = y;
idx++;
}
}
F0R(i,m) {
int l,r,y;
tie(l,r,y) = S[i];
int last = -1;
for (int b : buildingsOnSegment[i]) {
if (last != -1) {
int dist = abs(B[last].first - B[b].first);
int i1 = nodes[{ b, y }], i2 = nodes[{ last, y }];
adj[i1].push_back({ i2, dist });
adj[i2].push_back({ i1, dist });
}
last = b;
}
}
return djikstra(adj, nodes[{s,0}], nodes[{g,0}]);
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
// ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = sz(x), m = sz(l);
vtiii segs(m);
vpii B(n);
F0R(i, n) B[i] = {x[i], h[i]};
F0R(i, m) segs[i] = {l[i], r[i], y[i]};
return min_distance(B, segs, s, g);
}
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<int> x(n), h(n);
for (int i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
int s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccLNkM8q.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCoebTo.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
