# Best path using some intermediate points, where cost is either x-axis or y-axis distance

We are given N Cartesian points $(x, y)$. Anytime we move from $i$-th point to the $j$-th, the move costs $\min\left(\left|x_i - x_j\right|, \left|y_i - y_j\right|\right)$.

The problem is to calculate how much costs the cheapest path from point $1$ to the point $N$.

For example, for:

5
2 2
1 1
4 5
7 1
6 7


The answer is 2. We move from (2,2) to (7,1) with cost $\min\left(|7 - 2|, |1 - 2|\right) = \min(5, 1) = 1$, then from (7,1) to (6,7) with cost $\min(|6 - 7|, |7 - 1|) = 1$. And we get answer 2.

I have figured out that greedy algorithm approach is going to work well in this problem (I only want to move between points with the closest x and y by using Dijkstra's algorithm). Right now my program is working (I made ton of tests and compared outs to the "brute algorithm" outs), but it is too slow.

I am not sure if it is algorithm problem or problem with my code. In this task time complexity should by $O(n \cdot \log(n))$ and I think that my algorithm works with this speed. Could you help me?

I have written two codes, but both are too slow.

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int, long long> para;
int glob;
int wys = 0;
vector<vector< para > >wierz;
vector<long long> odl;
vector<para> by_x;
vector<para> by_y;
const long long max_ll = 23372036854775806;
void init(int n){
odl.resize(n, max_ll);
wierz.resize(n);
by_x.resize(n);
by_y.resize(n);
}

struct cmp{
bool operator() (const long &a, const long &b){
if(odl[a] < odl[b]) return true;
if(odl[b] > odl[a]) return false;
return (a < b);
}
};

set<long, cmp> Q;

void dijkstra(){
long v, u, c;
odl[0] = 0;
Q.insert(0);
while(!Q.empty()){
u = *(Q.begin());
Q.erase(Q.begin());
if(u != glob){
for(size_t i = 0; i < wierz[u].size(); i++){
v = wierz[u][i].first;
c = wierz[u][i].second;
if(odl[v] - c > odl[u] && odl[u] != max_ll){
odl[v] = odl[u] + c;
Q.insert(v);
}
}
}
}
}

void update(int i, int n){

long long odlx1 = abs(by_x[i].first - by_x[i - 1].first);
long long odly1 = abs(by_y[i].first - by_y[i - 1].first);
wierz[by_x[i].second].push_back(make_pair(by_x[i - 1].second, odlx1));
wierz[by_x[i - 1].second].push_back(make_pair(by_x[i].second, odlx1));
wierz[by_y[i].second].push_back(make_pair(by_y[i - 1].second, odly1));
wierz[by_y[i - 1].second].push_back(make_pair(by_y[i].second, odly1));

}

int main(){
std::ios::sync_with_stdio(false);
long long n;
cin>>n;
glob = n - 1;
init(n);
long long a;
long long b;
pair<long long, int> p, p2;
for(int i = 0; i < n; i++){
cin>>a;
cin>>b;
by_x[i] = make_pair(a, i);
by_y[i] =  make_pair(b, i);
}

sort(by_x.begin(), by_x.end());
sort(by_y.begin(), by_y.end());
for(int i = 1; i < n; i++){
update(i, n);
}
dijkstra();
cout<<odl[n - 1]<<"\n";
return 0;
}


And the second code:

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include <cstdio>

int n;
std::vector< std::vector< std::pair<long, long> > >wierz;
std::vector< std::pair<long, long> > wej;
std::vector<long> odl;
const long max_ll = 2147483646;

struct cmp{
bool operator() (const long &a, const long &b){
if(odl[a] < odl[b]) return true;
if(odl[b] > odl[a]) return false;
return (a < b);
}
};

std::set<long, cmp> Q;

void dijkstra(){
long v, u, c;
odl[0] = 0;
Q.insert(0);
while(!Q.empty()){
u = *(Q.begin());
Q.erase(Q.begin());
for(size_t i = 0; i < wierz[u].size(); i++){
v = wierz[u][i].first;
c = wierz[u][i].second;
if(odl[v] - c > odl[u] && odl[u] != max_ll){
odl[v] = odl[u] + c;
Q.insert(v);
}
}
}
}

void update(std::vector<int> &wsk){
long odl;
int fst;
int sd;
for(int i = 1; i < n; i++){
fst = wsk[i];
sd = wsk[i - 1];
odl = std::min(std::abs(wej[fst].first - wej[sd].first),
std::abs(wej[fst].second - wej[sd].second));
wierz[fst].push_back(std::make_pair(sd, odl));
wierz[sd].push_back(std::make_pair(fst, odl));
}
}

bool cmp_x(const int a, const int b){
if(wej[a].first < wej[b].first) return true;
if(wej[a].first > wej[b].first) return false;
return wej[a].second < wej[b].second;
}

void sort_x(std::vector<int> &wsk){
sort(wsk.begin(), wsk.end(), cmp_x);
}

bool cmp_y(const int a, const int b){
if(wej[a].second < wej[b].second) return true;
if(wej[a].second > wej[b].second) return false;
return wej[a].first < wej[b].first;
}

void sort_y(std::vector<int> &wsk){
sort(wsk.begin(), wsk.end(), cmp_y);
}

int main(){
std::vector<int> wsk;
scanf("%d", &n);
odl.resize(n, max_ll);
wierz.resize(n);
wej.resize(n);
wsk.resize(n);
for(int i = 0; i < n; i++){
scanf("%ld %ld", &wej[i].first, &wej[i].second);
wsk[i] = i;
}
sort_x(wsk);
update(wsk);
sort_y(wsk);
update(wsk);
dijkstra();
printf("%ld\n", odl[n - 1]);
return 0;
}


I also tried with sets as positions savers but that also doesn't work fast enough.