Camp ( LQDOJ )

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <climits>
#include <queue>
using namespace std;
const int N = 1e3, INF = 2e9;
struct T
{
    int x, y;
};
T a[N+1], b[N+1];
int n, dp[N+1][N+1][2], m;
int dis (const T & q, const T & u)
{
    return (q.x - u.x)*(q.x - u.x) + (q.y - u.y)*(q.y - u.y);
}
void read()
{
   cin >> n >> m;
   for (int i = 1; i <= n; ++ i)
   {
       cin >> a[i].x >> a[i].y;
   }
   for (int i = 1; i <= m; ++ i)
   {
       cin >> b[i].x >> b[i].y;
   }
   for (int i = 0; i <= n; ++ i)
   {
       for (int j = 0; j <= m; ++ j)
       {
           dp[i][j][0] = INF;
           dp[i][j][1] = INF;
       }
   }
}
void Minimize(int & a, int b)
{
    a = min(a, b);
}
void solve()
{
   dp[1][0][0] = 0;
   dp[1][1][1] = dis(a[1], b[1]);
   for (int j = 2; j <= m; ++ j)
   {
       dp[1][j][1] = dp[1][j-1][1] + dis(b[j], b[j - 1]);
   }
   for (int i = 2; i <= n; ++ i)
   {
       dp[i][0][0] = dp[i-1][0][0] + dis(a[i], a[i-1]);
   }
   for (int i = 1; i <= n; ++ i)
   {
       for (int j = 1; j <= m; ++ j)
       {
           Minimize(dp[i][j][0], dp[i-1][j][0] + dis(a[i], a[i-1]));
           Minimize(dp[i][j][0], dp[i-1][j][1] + dis(b[j], a[i]));
           Minimize(dp[i][j][1], dp[i][j-1][1] + dis(b[j], b[j-1]));
           Minimize(dp[i][j][1], dp[i][j-1][0] + dis(a[i], b[j]));
       }
   }
   cout << dp[n][m][0];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    solve();
}