fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
  4. #define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ALL(A) A.begin(), A.end()
  9. #define SZ(A) (int)(A).size()
  10. const int N = (int) 1e5 + 5;
  11. const int dx[] = {0, 0, - 1, 1};
  12. const int dy[] = {1, - 1, 0, 0};
  13.  
  14. int n, m, k, q;
  15. char a[15][10005];
  16.  
  17. struct Portals {
  18.     int x, y, u, v, w;
  19.     void input() {
  20.         cin >> x >> y >> u >> v >> w;
  21.     }
  22. } port[15];
  23. long long ans[100005];
  24. vector <array <int, 3>> g[15][10005];
  25. long long dist[15][15][10005];
  26.  
  27. void dijkstra(int id) {
  28.     FOR(i, 1, n) FOR(j, 1, m) {
  29.         dist[id][i][j] = 1e18;
  30.     }
  31.     #define bg array <long long, 4>
  32.     priority_queue <bg, vector <bg>, greater <bg>> pq;
  33.  
  34.     dist[id][port[id].x][port[id].y] = 0;
  35.     pq.push({0, id, port[id].x, port[id].y});
  36.  
  37.     while (!pq.empty()) {
  38.         auto [cost, id, u, v] = pq.top();
  39.         pq.pop();
  40.         if (cost > dist[id][u][v]) continue;
  41.         FOR(s, 0, 3) {
  42.             int x = u + dx[s], y = v + dy[s];
  43.             if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '#') continue;
  44.             if (dist[id][x][y] > cost + 1) {
  45.                 dist[id][x][y] = cost + 1;
  46.                 pq.push({cost + 1, id, x, y});
  47.             }
  48.         }
  49.         for (auto it : g[u][v]) {
  50.             int x = it[0], y = it[1], w = it[2];
  51.             if (dist[id][x][y] > cost + w) {
  52.                 dist[id][x][y] = cost + w;
  53.                 pq.push({cost + w, id, x, y});
  54.             }
  55.         }
  56.     }
  57. }
  58.  
  59. void bfs(int id, int l, int r, int xx, int yy) {
  60.     FOR(i, 1, n) FOR(j, l, r) {
  61.         dist[id][i][j] = 1e18;
  62.     }
  63.  
  64.     queue <pair <int, int>> q;
  65.     dist[id][xx][yy] = 0;
  66.     q.push({xx, yy});
  67.  
  68.     while (!q.empty()) {
  69.         auto [u, v] = q.front(); q.pop();
  70.  
  71.         FOR(s, 0, 3) {
  72.             int x = u + dx[s], y = v + dy[s];
  73.             if (x < 1 || x > n || y < l || y > r || a[x][y] == '#') continue;
  74.             if (dist[id][x][y] > dist[id][u][v] + 1) {
  75.                 dist[id][x][y] = dist[id][u][v] + 1;
  76.                 q.push({x, y});
  77.             }
  78.         }
  79.     }
  80. }
  81.  
  82. void DAC(int L, int R, vector <array <int, 5>> &cur) {
  83.     if (L > R) return;
  84.     if (cur.empty()) return;
  85.  
  86.     int mid = L + R >> 1;
  87.     if (L == R) {
  88.         FOR(i, 1, n) if (a[i][L] != '#') {
  89.             bfs(i, L, R, i, R);
  90.         }
  91.         for (auto x : cur) {
  92.             /// cout << dist[L][x[0]][x[1]] << " " << dist[L][x[2]][x[3]] << '\n';
  93.             FOR(i, 1, n) if (a[i][mid] == '.') {
  94.                 ans[x[4]] = min(ans[x[4]], dist[i][x[0]][x[1]] + dist[i][x[2]][x[3]]);
  95.             }
  96.         }
  97.         return;
  98.     }
  99.  
  100.     vector <array <int, 5>> le, ri, mi;
  101.  
  102.     for (auto x : cur) {
  103.         /// x y u v i d
  104.         if (x[3] <= mid) le.push_back(x);
  105.         else if (x[1] >= mid + 1) ri.push_back(x);
  106.         else mi.push_back(x);
  107.     }
  108.  
  109.     FOR(i, 1, n) if (a[i][mid] == '.') {
  110.         bfs(i, L, R, i, mid);
  111.     }
  112.  
  113.     for (auto x : mi) {
  114.         FOR(i, 1, n) if (a[i][mid] == '.') {
  115.             ans[x[4]] = min(ans[x[4]], dist[i][x[0]][x[1]] + dist[i][x[2]][x[3]]);
  116.         }
  117.     }
  118.  
  119.     for (auto x : le) {
  120.         FOR(i, 1, n) if (a[i][mid] == '.') {
  121.             FOR(j, 1, n) if (a[j][mid] == '.') {
  122.                 ans[x[4]] = min(ans[x[4]], dist[i][x[0]][x[1]] + dist[i][j][mid] + dist[j][x[2]][x[3]]);
  123.             }
  124.         }
  125.     }
  126.  
  127.     for (auto x : ri) {
  128.         FOR(i, 1, n) if (a[i][mid] == '.') {
  129.             FOR(j, 1, n) if (a[j][mid] == '.') {
  130.                 ans[x[4]] = min(ans[x[4]], dist[i][x[0]][x[1]] + dist[i][j][mid] + dist[j][x[2]][x[3]]);
  131.             }
  132.         }
  133.     }
  134.  
  135.     DAC(L, mid, le);
  136.     DAC(mid + 1, R, ri);
  137. }
  138.  
  139. signed main () {
  140.     ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  141.     #define ko "maze"
  142.     if (fopen(ko".inp", "r")) {
  143.         freopen(ko".inp", "r", stdin);
  144.         freopen(ko".out", "w", stdout);
  145.     }
  146.     cin >> n >> m >> k >> q;
  147.     FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
  148.     FOR(i, 1, k) port[i].input();
  149.     FOR(i, 1, q) ans[i] = 1e18;
  150.     FOR(i, 1, k) {
  151.         auto [x, y, u, v, w] = port[i];
  152.         g[x][y].push_back({u, v, w});
  153.         g[u][v].push_back({x, y, w});
  154.     }
  155.     FOR(i, 1, k) dijkstra(i);
  156.  
  157.     vector <array <int, 5>> query;
  158.     FOR(i, 1, q) {
  159.         int x, y, u, v; cin >> x >> y >> u >> v;
  160.         if (a[x][y] == '#') continue;
  161.         if (a[u][v] == '#') continue;
  162.         FOR(id, 1, k) {
  163.             ans[i] = min(ans[i], dist[id][x][y] + dist[id][u][v]);
  164.         }
  165.         if (y > v) {
  166.             swap(x, u);
  167.             swap(y, v);
  168.         }
  169.         query.push_back({x, y, u, v, i});
  170.     }
  171.  
  172.     DAC(1, m, query);
  173.  
  174.     FOR(i, 1, q) {
  175.         if (ans[i] >= 1e18) cout << - 1 << '\n';
  176.         else cout << ans[i] << '\n';
  177.     }
  178.  
  179.     return 0;
  180. }
  181.  
  182.  
Success #stdin #stdout 0.01s 7804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/70Zfm1
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!