YEZAELP

o59_mar_c2_wormholes (Floyd-Warshall)

Dec 6th, 2021
634
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int K = 30 + 10;
  6. using pi = pair <int, int>;
  7. struct Hole{int x1, y1, x2, y2;};
  8. struct Point{int x, y;};
  9. vector <pi> point;
  10. Hole hole[K];
  11. int sz;
  12.  
  13. int Index(int x, int y){
  14.     int l = 0, r = sz - 1;
  15.     while(l <= r){
  16.         int mid = (l + r) / 2;
  17.         if(point[mid].first == x and point[mid].second == y) return mid;
  18.         else if(point[mid].first == x){
  19.             if(point[mid].second < y) l = mid + 1;
  20.             else r = mid - 1;
  21.         }
  22.         else if(point[mid].first < x) l = mid + 1;
  23.         else r = mid - 1;
  24.     }
  25. }
  26.  
  27. int Dist(int x1, int y1, int x2, int y2){
  28.     return abs(x1 - x2) + abs(y1 - y2);
  29. }
  30.  
  31. int main(){
  32.  
  33.     int k,Q;
  34.     scanf("%d %d", &k, &Q);
  35.  
  36.     for(int i=1;i<=k;i++){
  37.         int x1, y1, x2, y2;
  38.         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
  39.         hole[i] = {x1, y1, x2, y2};
  40.         point.push_back({x1, y1});
  41.         point.push_back({x2, y2});
  42.     }
  43.  
  44.     sort(point.begin(), point.end());
  45.     point.resize( unique(point.begin(), point.end()) - point.begin());
  46.     sz = point.size();
  47.  
  48.     int dis[sz + 1][sz + 1];
  49.     for(int i=0;i<sz;i++){
  50.         for(int j=0;j<sz;j++){
  51.             dis[i][j] = (i == j ? 0:
  52.                          Dist(point[i].first, point[i].second, point[j].first, point[j].second));
  53.         }
  54.     }
  55.  
  56.     for(int i=1;i<=k;i++){
  57.         int idx1 = Index(hole[i].x1, hole[i].y1);
  58.         int idx2 = Index(hole[i].x2, hole[i].y2);
  59.         dis[ idx1 ][ idx2 ] = dis[ idx2 ][ idx1 ] = 0;
  60.     }
  61.  
  62.     for(int k=0;k<sz;k++){
  63.         for(int i=0;i<sz;i++){
  64.             for(int j=0;j<sz;j++){
  65.                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  66.             }
  67.         }
  68.     }
  69.  
  70.  
  71.     for(int q=1;q<=Q;q++){
  72.         int ux, uy, vx, vy;
  73.         scanf("%d %d %d %d", &ux, &uy, &vx, &vy);
  74.         int mn = Dist(ux, uy, vx, vy);
  75.         for(int i=0;i<sz;i++){
  76.             for(int j=i+1;j<sz;j++){
  77.                 mn = min({mn,
  78.                           Dist(ux, uy, point[i].first, point[i].second) + dis[i][j] + Dist(point[j].first, point[j].second, vx, vy),
  79.                           Dist(vx, vy, point[i].first, point[i].second) + dis[i][j] + Dist(point[j].first, point[j].second, ux, uy)
  80.                          });
  81.             }
  82.         }
  83.         printf("%d\n", mn);
  84.     }
  85.  
  86.     return 0;
  87. }
RAW Paste Data