#ifndef _DEBUG
#include "walk.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
struct Bridge
{
int l, r, h;
bool operator<(Bridge other)
{
return vector<int>{l, r, h} < vector<int>{other.l, other.r, other.h};
}
};
long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g)
{
map<pair<int, int>, vector<pair<int, pair<int, int>>>> adj;
vector<Bridge> bridges;
for (int i = 0; i < l.size(); i++)
{
bridges.push_back({x[l[i]], x[r[i]], y[i]});
}
sort(bridges.begin(), bridges.end());
reverse(bridges.begin(), bridges.end());
set<pair<int, int>> active;
set<pair<int, int>> active_by_h;
map<int, int> last_at_height;
int i = 0;
for (int b : x)
{
while (active.size() && active.begin()->first < b)
{
active_by_h.erase({active.begin()->second, active.begin()->first});
active.erase(active.begin());
}
for (auto [H, end] : active_by_h)
{
if (H > int(h[i]))
break;
int last = last_at_height[H];
adj[{b, H}].push_back({abs(last - b), {last, H}});
adj[{last, H}].push_back({abs(last - b), {b, H}});
}
while (bridges.size() && bridges.back().l == b)
{
assert(bridges.back().h <= h[i]);
active.insert({bridges.back().r, bridges.back().h});
active_by_h.insert({bridges.back().h, bridges.back().r});
bridges.pop_back();
}
int lasth = 0;
for (auto [H, end] : active_by_h)
{
if (H > int(h[i])
break;
adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
adj[{b, H}].push_back({abs(H - lasth), {b, lasth}});
lasth = H;
last_at_height[H] = b;
}
i++;
}
assert(bridges.size() == 0);
priority_queue<tuple<int, int, int>> pq;
pq.push(tuple<int, int, int>{0, x[s], 0});
map<pair<int, int>, int> dist;
while (pq.size())
{
auto [d, px, py] = pq.top();
pq.pop();
if (dist.count({px, py}))
continue;
dist[{px, py}] = -d;
for (auto [plusd, c] : adj[{px, py}])
{
if (dist.count(c) == 0)
pq.push(tuple<int, int, int>{d - plusd, c.first, c.second});
}
}
if (dist.count({x[g], 0}) == 0)
return -1;
return dist[{x[g], 0}];
}
#ifdef _DEBUG
signed main()
{
signed n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<signed> x(n), h(n);
for (signed i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<signed> l(m), r(m), y(m);
for (signed i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
signed s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
cerr << result << "\n";
fclose(stdout);
return 0;
}
#endif
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < l.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:67:21: error: expected ';' before 'break'
67 | if (H > int(h[i])
| ^
| ;
68 | break;
| ~~~~~
walk.cpp:67:10: warning: value computed is not used [-Wunused-value]
67 | if (H > int(h[i])
| ~~^~~~~~~~~~~
walk.cpp:69:55: error: expected ')' before ';' token
69 | adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
| ^
| )
walk.cpp:67:7: note: to match this '('
67 | if (H > int(h[i])
| ^
walk.cpp:69:29: error: could not convert '(& adj.std::map<std::pair<long int, long int>, std::vector<std::pair<long int, std::pair<long int, long int> > > >::operator[](std::pair<long int, long int>(b, lasth)))->std::vector<std::pair<long int, std::pair<long int, long int> > >::push_back(std::pair<long int, std::pair<long int, long int> >(std::abs((H - lasth)), std::pair<long int, long int>(b, (* & H))))' from 'void' to 'bool'
69 | adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| |
| void
