#include <bits/stdc++.h>
#include "walk.h"
#define msize 2500000
#define MAX 9223372036854775806
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[msize];
ll isq[msize];
vector<vi> G;
void dijktra(ll u){
memset(isq,0,sizeof isq);
for(int i=0;i<=msize;i++){
dist[i]=MAX;
}
priority_queue<ii,vi,greater<ii> > pq;
dist[u]=0;
isq[u]=1;
pq.push(ii(0,u));
while(!pq.empty()){
ll x=pq.top().second;
ll di=pq.top().first;
pq.pop();
isq[x]=0;
// if(di>dist[x]) continue;
for(auto &v:G[x]){
ll w=v.first;
if(dist[v.second]>dist[x]+w){
dist[v.second]=dist[x]+w;
if(isq[v.second]==0){
pq.push(ii(dist[v.second],v.second));
isq[v.second]=1;
}
}
}
}
}
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 no;
no=0;
map<ii,ll> m;
G.resize(msize);
vi aux;
for(int i=0;i<y.size();i++){
ll ant=-1,id;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
if(m[ii(x[j],y[i])]==0){
no++;
m[ii(x[j],y[i])]=no;
}
aux.push_back(ii(x[j],y[i]));
if(ant==-1){
ant=m[ii(x[j],y[i])];
id=j;
}
else{
ll dis=abs(x[j]-x[id]);
ll u=m[ii(x[j],y[i])];
G[ant].push_back(ii(dis,u));
G[u].push_back(ii(dis,ant));
ant=u;
id=j;
}
}
}
}
if(m[ii(x[s],0)]==0){
no++;
m[ii(x[s],0)]=no;
aux.push_back(ii(x[s],0));
}
if(m[ii(x[g],0)]==0){
no++;
m[ii(x[g],0)]=no;
aux.push_back(ii(x[g],0));
}
sort(aux.begin(),aux.end());
for(int i=1;i<aux.size();i++){
if(aux[i].first==aux[i-1].first){
int u=m[ii(aux[i].first,aux[i].second)];
int v=m[ii(aux[i-1].first,aux[i-1].second)];
int w=abs(aux[i].second-aux[i-1].second);
G[u].push_back(ii(w,v));
G[v].push_back(ii(w,u));
}
}
dijktra(m[ii(x[s],0)]);
if(dist[m[ii(x[g],0)]]==MAX) dist[m[ii(x[g],0)]]=-1;
ll res=dist[m[ii(x[g],0)]];
return res;
}
#include <bits/stdc++.h>
#include "walk.h"
#define msize 2500000
#define MAX 9223372036854775806
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[msize];
ll isq[msize];
vector<vi> G;
void dijktra(ll u){
memset(isq,0,sizeof isq);
for(int i=0;i<=msize;i++){
dist[i]=MAX;
}
priority_queue<ii,vi,greater<ii> > pq;
dist[u]=0;
isq[u]=1;
pq.push(ii(0,u));
while(!pq.empty()){
ll x=pq.top().second;
ll di=pq.top().first;
pq.pop();
isq[x]=0;
// if(di>dist[x]) continue;
for(auto &v:G[x]){
ll w=v.first;
if(dist[v.second]>dist[x]+w){
dist[v.second]=dist[x]+w;
if(isq[v.second]==0){
pq.push(ii(dist[v.second],v.second));
isq[v.second]=1;
}
}
}
}
}
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 no;
no=0;
map<ii,ll> m;
G.resize(msize);
vi aux;
for(int i=0;i<y.size();i++){
ll ant=-1,id;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
if(m[ii(x[j],y[i])]==0){
no++;
m[ii(x[j],y[i])]=no;
}
aux.push_back(ii(x[j],y[i]));
if(ant==-1){
ant=m[ii(x[j],y[i])];
id=j;
}
else{
ll dis=abs(x[j]-x[id]);
ll u=m[ii(x[j],y[i])];
G[ant].push_back(ii(dis,u));
G[u].push_back(ii(dis,ant));
ant=u;
id=j;
}
}
}
}
if(m[ii(x[s],0)]==0){
no++;
m[ii(x[s],0)]=no;
aux.push_back(ii(x[s],0));
}
if(m[ii(x[g],0)]==0){
no++;
m[ii(x[g],0)]=no;
aux.push_back(ii(x[g],0));
}
sort(aux.begin(),aux.end());
for(int i=1;i<aux.size();i++){
if(aux[i].first==aux[i-1].first){
int u=m[ii(aux[i].first,aux[i].second)];
int v=m[ii(aux[i-1].first,aux[i-1].second)];
int w=abs(aux[i].second-aux[i-1].second);
G[u].push_back(ii(w,v));
G[v].push_back(ii(w,u));
}
}
dijktra(m[ii(x[s],0)]);
if(dist[m[ii(x[g],0)]]==MAX) dist[m[ii(x[g],0)]]=-1;
ll res=dist[m[ii(x[g],0)]];
return res;
}
Compilation message
walk.cpp: In function 'void dijktra(ll)':
walk.cpp:23:8: warning: unused variable 'di' [-Wunused-variable]
23 | ll di=pq.top().first;
| ^~
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:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<y.size();i++){
| ~^~~~~~~~~
walk.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=1;i<aux.size();i++){
| ~^~~~~~~~~~~
walk.cpp: At global scope:
walk.cpp:102:4: error: redefinition of 'll dist [2500000]'
102 | ll dist[msize];
| ^~~~
walk.cpp:9:4: note: 'll dist [2500000]' previously declared here
9 | ll dist[msize];
| ^~~~
walk.cpp:103:4: error: redefinition of 'll isq [2500000]'
103 | ll isq[msize];
| ^~~
walk.cpp:10:4: note: 'll isq [2500000]' previously declared here
10 | ll isq[msize];
| ^~~
walk.cpp:104:12: error: redefinition of 'std::vector<std::vector<std::pair<long long int, long long int> > > G'
104 | vector<vi> G;
| ^
walk.cpp:11:12: note: 'std::vector<std::vector<std::pair<long long int, long long int> > > G' previously declared here
11 | vector<vi> G;
| ^
walk.cpp:105:6: error: redefinition of 'void dijktra(ll)'
105 | void dijktra(ll u){
| ^~~~~~~
walk.cpp:12:6: note: 'void dijktra(ll)' previously defined here
12 | void dijktra(ll u){
| ^~~~~~~
walk.cpp: In function 'void dijktra(ll)':
walk.cpp:116:8: warning: unused variable 'di' [-Wunused-variable]
116 | ll di=pq.top().first;
| ^~
walk.cpp: At global scope:
walk.cpp:132:11: error: redefinition of 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)'
132 | 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) {
| ^~~~~~~~~~~~
walk.cpp:39:11: note: 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)' previously defined here
39 | 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) {
| ^~~~~~~~~~~~
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:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0;i<y.size();i++){
| ~^~~~~~~~~
walk.cpp:173:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int i=1;i<aux.size();i++){
| ~^~~~~~~~~~~
