mickypinata

IPST59: Wormholes

Jun 25th, 2021 (edited)
1,032
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 30;
  5.  
  6. typedef pair<int, int> pii;
  7.  
  8. map<pii, int> coorToIdx;
  9. pii coor[N + N];
  10. vector<int> adj[N + N];
  11. int dist[N + N][N + N];
  12.  
  13. int nVertex = 0;
  14. int addCoor(int x, int y){
  15.     map<pii, int>::iterator itr = coorToIdx.find(pii(x, y));
  16.     if(itr == coorToIdx.end()){
  17.         coorToIdx.emplace(pii(x, y), nVertex);
  18.         coor[nVertex] = pii(x, y);
  19.         return nVertex++;
  20.     }
  21.     return itr -> second;
  22. }
  23.  
  24. int distance(pii &u, pii &v){
  25.     return abs(u.first - v.first) + abs(u.second - v.second);
  26. }
  27.  
  28. int main(){
  29.  
  30.     int nPortal, Q;
  31.     scanf("%d%d", &nPortal, &Q);
  32.     for(int i = 1; i <= nPortal; ++i){
  33.         int x1, y1, x2, y2;
  34.         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  35.         int u = addCoor(x1, y1);
  36.         int v = addCoor(x2, y2);
  37.         adj[u].push_back(v);
  38.         adj[v].push_back(u);
  39.     }
  40.  
  41.     for(int u = 0; u < nVertex; ++u){
  42.         for(int v = 0; v < nVertex; ++v){
  43.             dist[u][v] = distance(coor[u], coor[v]);
  44.         }
  45.     }
  46.     for(int u = 0; u < nVertex; ++u){
  47.         for(int v : adj[u]){
  48.             dist[u][v] = 0;
  49.         }
  50.     }
  51.  
  52.     // Floyd-Warshall Algorithm
  53.     for(int k = 0; k < nVertex; ++k){
  54.         for(int u = 0; u < nVertex; ++u){
  55.             for(int v = 0; v < nVertex; ++v){
  56.                 dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
  57.             }
  58.         }
  59.     }
  60.  
  61.     // Query
  62.     for(int q = 1; q <= Q; ++q){
  63.         int x1, y1, x2, y2;
  64.         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  65.         pii st = pii(x1, y1);
  66.         pii ed = pii(x2, y2);
  67.         int ans = distance(st, ed);
  68.         for(int u = 0; u < nVertex; ++u){
  69.             for(int v = 0; v < nVertex; ++v){
  70.                 if(u == v){
  71.                     continue;
  72.                 }
  73.                 ans = min(ans, distance(st, coor[u]) + dist[u][v] + distance(coor[v], ed));
  74.             }
  75.         }
  76.         cout << ans << '\n';
  77.     }
  78.  
  79.     return 0;
  80. }
  81.  
RAW Paste Data