3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.