Guest User

Kodi zadachai B 10/10 usaco 19.12.2016 Div.Gold

a guest
Dec 19th, 2016
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.62 KB | None | 0 0
  1. # include <bits/stdc++.h>
  2. # define IoS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  3. # define Typ long long
  4.   using namespace std;
  5.   long long h, g, pi = 100000000000000ll;
  6.   long long hrr[1010][3], grr[1010][3], dp[3][1010][1010];
  7.   deque< pair< int, pair< int, int > > > deq_a;
  8.   inline long long rast(long long x1, long long y1, long long x2, long long y2)
  9.   {
  10.       return ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1));
  11.   }
  12.   int main()
  13.   {
  14.       IoS; freopen("checklist.in", "r", stdin); freopen("checklist.out", "w", stdout);
  15.       long long i, j, x, y, k;
  16.       cin >> h >> g;
  17.       for(i = 1; i <= h; i++){
  18.         cin >> hrr[i][1] >> hrr[i][2];
  19.       }
  20.       for(i = 1; i <= g; i++){
  21.         cin >> grr[i][1] >> grr[i][2];
  22.       }
  23.       for(i = 0; i <= h; i++){
  24.         for(j = 0; j <= g; j++){
  25.             dp[1][i][j] = dp[2][i][j] = pi;
  26.         }
  27.       }
  28.       deq_a.push_back({1, {1, 0}});
  29.       dp[1][1][0] = 0;
  30.       while(deq_a.size() > 0){
  31.         k = deq_a.front().first;
  32.         x = deq_a.front().second.first;
  33.         y = deq_a.front().second.second;
  34.         ///cout << " k = " << k << " x = " << x << " y = " << y << '\n';
  35.         deq_a.pop_front();
  36.         if((x > h) || (y > g)) continue;
  37.         if((x == h) && (y == g)){
  38.             if(k == 1) continue;
  39.             else if(dp[1][x][y] > dp[2][x][y] + rast(hrr[x][1], hrr[x][2], grr[y][1], grr[y][2])){
  40.                 dp[1][x][y] = dp[2][x][y] + rast(hrr[x][1], hrr[x][2], grr[y][1], grr[y][2]);
  41.                 deq_a.push_back({1, {x, y}});
  42.             }
  43.         }
  44.         else if(k == 1){
  45.             if((x == h) && (y != g)) continue;
  46.             else if(y == g){
  47.                 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])){
  48.                     dp[1][x + 1][y] = dp[k][x][y] + rast(hrr[x][1], hrr[x][2], hrr[x + 1][1], hrr[x + 1][2]);
  49.                     deq_a.push_back({1, {x + 1, y}});
  50.                 }
  51.             }
  52.             else {
  53.                 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])){
  54.                     dp[1][x + 1][y] = dp[k][x][y] + rast(hrr[x][1], hrr[x][2], hrr[x + 1][1], hrr[x + 1][2]);
  55.                     deq_a.push_back({1, {x + 1, y}});
  56.                 }
  57.                 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])){
  58.                     dp[2][x][y + 1] = dp[k][x][y] + rast(hrr[x][1], hrr[x][2], grr[y + 1][1], grr[y + 1][2]);
  59.                     deq_a.push_back({2, {x, y + 1}});
  60.                 }
  61.             }
  62.         }
  63.         else {
  64.             if(y == g){
  65.                 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])){
  66.                     dp[1][x + 1][y] = dp[k][x][y] + rast(grr[y][1], grr[y][2], hrr[x + 1][1], hrr[x + 1][2]);
  67.                     deq_a.push_back({1, {x + 1, y}});
  68.                 }
  69.             }
  70.             else {
  71.                 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])){
  72.                     dp[2][x][y + 1] = dp[k][x][y] + rast(grr[y][1], grr[y][2], grr[y + 1][1], grr[y + 1][2]);
  73.                     deq_a.push_back({2, {x, y + 1}});
  74.                 }
  75.                 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])){
  76.                     dp[1][x + 1][y] = dp[k][x][y] + rast(grr[y][1], grr[y][2], hrr[x + 1][1], hrr[x + 1][2]);
  77.                     deq_a.push_back({1, {x + 1, y}});
  78.                 }
  79.             }
  80.         }
  81.       }
  82.       cout << dp[1][h][g];
  83.       return 0;
  84.   }
Add Comment
Please, Sign In to add comment