Submission #881366

#	Time	Username	Problem	Language	Result	Execution time	Memory
881366		MilosMilutinovic	Soccer (JOI17_soccer)	C++14	100 / 100	601 ms	115016 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  h += 1;
  w += 1;
  int a, b, c;
  cin >> a >> b >> c;
  int n;
  cin >> n;
  vector<int> s(n), t(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i] >> t[i];
  }
  int ver = 3 * h * w;
  auto Id = [&](int x, int y, int t) {
    return (x * w + y) * 3 + t;
  };
  vector<vector<int>> f(h, vector<int>(w, -1));
  {
    vector<pair<int, int>> que;
    for (int i = 0; i < n; i++) {
      que.emplace_back(s[i], t[i]);
      f[s[i]][t[i]] = 0;
    }
    auto Valid = [&](int x, int y) {
      return 0 <= x && x < h && 0 <= y && y < w;
    };
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b].first;
      int y = que[b].second;
      for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (Valid(nx, ny) && f[nx][ny] == -1) {
          f[nx][ny] = f[x][y] + 1;
          que.emplace_back(nx, ny);
        }
      }
    }
  }
  vector<vector<pair<int, long long>>> g(ver);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i > 0) {
        g[Id(i, j, 0)].emplace_back(Id(i - 1, j, 0), a);
        g[Id(i, j, 2)].emplace_back(Id(i - 1, j, 2), c);
      }
      if (i + 1 < h) {
        g[Id(i, j, 0)].emplace_back(Id(i + 1, j, 0), a);
        g[Id(i, j, 2)].emplace_back(Id(i + 1, j, 2), c);
      }
      if (j > 0) {
        g[Id(i, j, 1)].emplace_back(Id(i, j - 1, 1), a);
        g[Id(i, j, 2)].emplace_back(Id(i, j - 1, 2), c);
      }
      if (j + 1 < w) {
        g[Id(i, j, 1)].emplace_back(Id(i, j + 1, 1), a);
        g[Id(i, j, 2)].emplace_back(Id(i, j + 1, 2), c);
      }
      g[Id(i, j, 2)].emplace_back(Id(i, j, 0), b);
      g[Id(i, j, 2)].emplace_back(Id(i, j, 1), b);
      g[Id(i, j, 0)].emplace_back(Id(i, j, 2), f[i][j] * 1LL * c);
      g[Id(i, j, 1)].emplace_back(Id(i, j, 2), f[i][j] * 1LL * c);
    }
  }
  const long long inf = (long long) 1e18;
  vector<long long> dist(ver, inf);
  dist[Id(s[0], t[0], 2)] = 0;
  set<pair<long long, int>> st;
  st.emplace(0LL, Id(s[0], t[0], 2));
  while (!st.empty()) {
    auto it = st.begin();
    int i = it->second;
    st.erase(it);
    for (auto& p : g[i]) {
      int to = p.first;
      long long w = p.second;
      if (dist[to] > dist[i] + w) {
        if (dist[to] != inf) {
          st.erase(st.find({dist[to], to}));
        }
        dist[to] = dist[i] + w;
        st.emplace(dist[to], to);
      }
    }
  }
  long long res = dist[Id(s[n - 1], t[n - 1], 2)];
  cout << (res == inf ? -1 : res) << '\n';
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65