Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <bits/stdc++.h>
- # define IoS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
- # define Typ long long
- using namespace std;
- long long h, g, pi = 100000000000000ll;
- long long hrr[1010][3], grr[1010][3], dp[3][1010][1010];
- deque< pair< int, pair< int, int > > > deq_a;
- inline long long rast(long long x1, long long y1, long long x2, long long y2)
- {
- return ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1));
- }
- int main()
- {
- IoS; freopen("checklist.in", "r", stdin); freopen("checklist.out", "w", stdout);
- long long i, j, x, y, k;
- cin >> h >> g;
- for(i = 1; i <= h; i++){
- cin >> hrr[i][1] >> hrr[i][2];
- }
- for(i = 1; i <= g; i++){
- cin >> grr[i][1] >> grr[i][2];
- }
- for(i = 0; i <= h; i++){
- for(j = 0; j <= g; j++){
- dp[1][i][j] = dp[2][i][j] = pi;
- }
- }
- deq_a.push_back({1, {1, 0}});
- dp[1][1][0] = 0;
- while(deq_a.size() > 0){
- k = deq_a.front().first;
- x = deq_a.front().second.first;
- y = deq_a.front().second.second;
- ///cout << " k = " << k << " x = " << x << " y = " << y << '\n';
- deq_a.pop_front();
- if((x > h) || (y > g)) continue;
- if((x == h) && (y == g)){
- if(k == 1) continue;
- else if(dp[1][x][y] > dp[2][x][y] + rast(hrr[x][1], hrr[x][2], grr[y][1], grr[y][2])){
- dp[1][x][y] = dp[2][x][y] + rast(hrr[x][1], hrr[x][2], grr[y][1], grr[y][2]);
- deq_a.push_back({1, {x, y}});
- }
- }
- else if(k == 1){
- if((x == h) && (y != g)) continue;
- else if(y == g){
- if(dp[1][x + 1][y] > dp[k][x][y] + rast(hrr[x][1], hrr[x][2], hrr[x + 1][1], hrr[x + 1][2])){
- dp[1][x + 1][y] = dp[k][x][y] + rast(hrr[x][1], hrr[x][2], hrr[x + 1][1], hrr[x + 1][2]);
- deq_a.push_back({1, {x + 1, y}});
- }
- }
- else {
- if(dp[1][x + 1][y] > dp[k][x][y] + rast(hrr[x][1], hrr[x][2], hrr[x + 1][1], hrr[x + 1][2])){
- dp[1][x + 1][y] = dp[k][x][y] + rast(hrr[x][1], hrr[x][2], hrr[x + 1][1], hrr[x + 1][2]);
- deq_a.push_back({1, {x + 1, y}});
- }
- if(dp[2][x][y + 1] > dp[k][x][y] + rast(hrr[x][1], hrr[x][2], grr[y + 1][1], grr[y + 1][2])){
- dp[2][x][y + 1] = dp[k][x][y] + rast(hrr[x][1], hrr[x][2], grr[y + 1][1], grr[y + 1][2]);
- deq_a.push_back({2, {x, y + 1}});
- }
- }
- }
- else {
- if(y == g){
- if(dp[1][x + 1][y] > dp[k][x][y] + rast(grr[y][1], grr[y][2], hrr[x + 1][1], hrr[x + 1][2])){
- dp[1][x + 1][y] = dp[k][x][y] + rast(grr[y][1], grr[y][2], hrr[x + 1][1], hrr[x + 1][2]);
- deq_a.push_back({1, {x + 1, y}});
- }
- }
- else {
- if(dp[2][x][y + 1] > dp[k][x][y] + rast(grr[y][1], grr[y][2], grr[y + 1][1], grr[y + 1][2])){
- dp[2][x][y + 1] = dp[k][x][y] + rast(grr[y][1], grr[y][2], grr[y + 1][1], grr[y + 1][2]);
- deq_a.push_back({2, {x, y + 1}});
- }
- if(dp[1][x + 1][y] > dp[k][x][y] + rast(grr[y][1], grr[y][2], hrr[x + 1][1], hrr[x + 1][2])){
- dp[1][x + 1][y] = dp[k][x][y] + rast(grr[y][1], grr[y][2], hrr[x + 1][1], hrr[x + 1][2]);
- deq_a.push_back({1, {x + 1, y}});
- }
- }
- }
- }
- cout << dp[1][h][g];
- return 0;
- }
Add Comment
Please, Sign In to add comment