#include using namespace std; typedef struct { int up_node_cost = INT_MAX; int low_node_cost = INT_MAX; // int up_node_y = INT_MAX; // int low_node_y = INT_MAX; }node; void print_v(vector v){ for(int i = 0; i < v.size();i++){ cout << v[i] << " "; } cout << endl; } int main(){ int n; cin >> n; map check_x; map > mp; // mp[X].first = min Y of X, mp[X].second = max Y of X vector xses; map columns; for(int i = 0; i < n; i++){ int x,y; cin >> x >> y; if(check_x[x] == 0){ mp[x].first = y; mp[x].second = y; xses.push_back(x); check_x[x] =1; } else{ mp[x].first = min(mp[x].first, y); mp[x].second = max(mp[x].second, y); } // cout << x << " " << mp[x].first << " " << mp[x].second << endl; // v.push_back(make_pair(x,y)); } // sort(v.begin(), v.end()); sort(xses.begin(), xses.end()); // print_v(xses); for(int i = 0; i < xses.size(); i++){ // print_v(xses); int x = xses[i]; // cout << "mp[x].first: " << mp[x].first << " \nmp[x].second: " << mp[x].second << endl; if( i == 0) { columns[x].low_node_cost = abs(mp[x].first - mp[x].second); columns[x].up_node_cost = abs(mp[x].first - mp[x].second); } else{ int prev_x = xses[i-1]; // print_v(xses); int sum = abs(prev_x - x); int sum1 = sum + abs(mp[prev_x].first - mp[x].first); // down to down int sum3 = sum + abs(mp[prev_x].second - mp[x].first); // up to down int sum2 = sum + abs(mp[prev_x].first - mp[x].second); // down to up int sum4 = sum + abs(mp[prev_x].second - mp[x].second); // up to up // cout << "prev_x: " << prev_x << "\nx: " << x << "\ni: " << i << endl; // cout << sum1 << " " << sum2 << " " << sum3 << " " << sum4 << endl; int sum_down = min(sum1,sum3); int sum_up = min(sum2,sum4); columns[x].low_node_cost = min(columns[x].low_node_cost,sum_down) + columns[prev_x].low_node_cost + abs(mp[x].first - mp[x].second); columns[x].up_node_cost = min(columns[x].up_node_cost,sum_up) + columns[prev_x].up_node_cost + abs(mp[x].first - mp[x].second); if(mp[x].first == mp[x].second){ columns[x].low_node_cost = min(columns[x].low_node_cost, columns[x].up_node_cost); columns[x].up_node_cost = min(columns[x].low_node_cost, columns[x].up_node_cost); } swap(columns[x].low_node_cost,columns[x].up_node_cost); // cout << min(columns[x].low_node_cost,sum_down) + columns[prev_x].low_node_cost << endl; // cout << min(columns[x].up_node_cost,sum_up) + columns[prev_x].up_node_cost << endl; } // cout << "x: " << x << endl; // cout << "columns[x].low_node_cost: " << columns[x].low_node_cost << "\ncolumns[x].up_node_cost: " << columns[x].up_node_cost << endl; // cout << endl; } cout << min(columns[xses[xses.size()-1]].low_node_cost,columns[xses[xses.size()-1]].up_node_cost) << endl; }