Two Robots

Easy

None

# Code

include < iostream >
include < sstream >
include < fstream >
include < vector >
include < cmath >
include < algorithm >

using namespace std;

define FOR(i,a,b) for(int i=a; i<=b; ++i)

const int MAX = 1e+9;
int dp[1001][1001];

class Test
{
public:
int m;
vector a, b;
int solve()
{
int n = a.size();
if (n == 0) return 0;
FOR(i, 2, n)
FOR(j, 1, m)
dp[i][j] = MAX;

``````    FOR(j, 1, m)
dp[1][j] = abs(b[0] - a[0]);

FOR(i, 2, n)
FOR(j, 1, m)
{
dp[i][b[i - 2]] = min(dp[i][b[i-2]], dp[i-1][j] + abs(j - a[i-1]) + abs(a[i-1] - b[i-1]));
dp[i][j] = min(dp[i][j], dp[i-1][j] + abs(b[i-2] - a[i-1]) + abs(a[i-1] - b[i-1]));
}
int sol = MAX;
FOR(j, 1, m)
sol = min(sol, dp[n][j]);
return sol;
}
friend istream & operator >> (istream & is, Test & test)
{
int n;
is >> test.m >> n;
FOR(i, 1, n)
{
int a, b;
is >> a >> b;
test.a.push_back(a);
test.b.push_back(b);
}
return is;
}
``````

};

vector tests;

int main()
{
int t;
cin >> t;
while (tâ€“)
{
Test test;
cin >> test;
cout << test.solve() << endl;
}
return 0;
}