#include "walk.h"
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
vector<pair<int, int>>re;
vector<pair<int, int>>link[2000100];
pair<int, int>bef[200100];
multiset<pair<int,int>>se;
long long dist[2000100];
int vis[2000100];
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)
{
int N = x.size();
int M = l.size();
int i;
int vc = 0;
for (i = 0; i < N; i++)
{
re.push_back({ x[i],i });
}
for (i = 0; i < M; i++)
{
re.push_back({ x[l[i]],-i-1 });
re.push_back({ x[r[i]] + 1,-i-M-1 });
}
sort(re.begin(), re.end());
int curv = N;
for (i = 0; i < re.size(); i++)
{
if (re[i].second >= 0)
{
int befh = 0;
int befv = re[i].second;
for (auto j = se.begin(); j != se.end(); j++)
{
if ((*j).first > h[re[i].second])
break;
int he = (*j).first;
link[befv].push_back({ curv,he - befh });
link[curv].push_back({ befv,he - befh });
int ve = (*j).second;
if (bef[ve].second)
{
link[bef[ve].second].push_back({ curv,re[i].first - bef[ve].first });
link[curv].push_back({ bef[ve].second,re[i].first - bef[ve].first });
}
bef[ve] = { re[i].first,curv };
befh = he;
befv = curv;
curv++;
}
}
else if (re[i].second >=-M)
{
int te = -re[i].second - 1;
se.insert({ y[te],te });
}
else
{
int te = -re[i].second - 1-M;
se.erase({ y[te],te });
}
}
memset(dist, 1, sizeof(dist));
priority_queue<pair<int, int>>pq;
pq.push({ 0,s });
while (pq.size())
{
auto a = pq.top();
pq.pop();
if (vis[a.second])
continue;
vis[a.second] = 1;
for (i = 0; i < link[a.second].size(); i++)
{
if (dist[link[a.second][i].first] > -a.first + link[a.second][i].second)
{
dist[link[a.second][i].first] = -a.first + link[a.second][i].second;
pq.push({ -dist[link[a.second][i].first],link[a.second][i].first });
}
}
}
return (dist[g]>(1LL<<50))?-1:dist[g];
}
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:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (i = 0; i < re.size(); i++)
| ~~^~~~~~~~~~~
walk.cpp:66:2: error: 'memset' was not declared in this scope
66 | memset(dist, 1, sizeof(dist));
| ^~~~~~
walk.cpp:5:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
4 | #include <queue>
+++ |+#include <cstring>
5 | using namespace std;
walk.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (i = 0; i < link[a.second].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
walk.cpp:17:6: warning: unused variable 'vc' [-Wunused-variable]
17 | int vc = 0;
| ^~
