Submission #631646

#	Time	Username	Problem	Language	Result	Execution time	Memory
631646		Abrar_Al_Samit	Soccer (JOI17_soccer)	C++17	30 / 100	331 ms	18588 KiB

soccer

#include<bits/stdc++.h>
using namespace std;

const int MX = 505;
const long long INF = 1e18;

int h, w;
int n; 
long long A, B, C;
long long nearest[MX][MX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
//0->down, 1->up, 2->right, 3->left
long long dist[MX][MX][5];
void PlayGround() {
  cin>>h>>w;
  cin>>A>>B>>C;
  cin>>n;

  for(int i=0; i<=h; ++i) {
    for(int j=0; j<=w; ++j) {
      nearest[i][j] = INF;

      for(int k=0; k<5; ++k) {
        dist[i][j][k] = INF;
      }
    }
  }

  auto valid = [&] (int i, int j) {
    return i<=h && i>-1 && j>-1 && j<=w;
  };

  vector<pair<int,int>>oneandn;

  queue<pair<int,int>>q;
  for(int i=0; i<n; ++i) {
    int x, y;
    cin>>x>>y;
    nearest[x][y] = 0;
    q.emplace(x, y);
    if(oneandn.size()==2) oneandn.pop_back();
    oneandn.emplace_back(x, y);
  }

  while(!q.empty()) {
    int x, y;
    tie(x, y) = q.front(); q.pop();
    for(int j=0; j<4; ++j) {
      int newx = x + dx[j], newy = y + dy[j];
      if(valid(newx, newy)) {
        if(nearest[newx][newy]>nearest[x][y]+1) {
          nearest[newx][newy] = nearest[x][y]+1;
          q.emplace(newx, newy);
        }
      }
    }
  }

  dist[oneandn[0].first][oneandn[0].second][0] = 0;
  priority_queue<tuple<long long, int, int, int>>pq;
  pq.emplace(0, oneandn[0].first, oneandn[0].second, 0);
  while(!pq.empty()) {
    long long cost;
    int x, y, dir;
    tie(cost, x, y, dir) = pq.top(); pq.pop();
    cost = -cost;
    if(cost!=dist[x][y][dir]) continue;

    if(dir) {
      int newx = x + dx[dir-1], newy = y + dy[dir-1];
      if(valid(newx, newy)) {
        if(dist[newx][newy][dir]>cost) { //continue travelling
          dist[newx][newy][dir] = cost;
          pq.emplace(-cost, newx, newy, dir);
        }
      }
      if(dist[x][y][0]>cost+nearest[x][y]*C) { //stop and call a player
        dist[x][y][0] = cost+nearest[x][y]*C;
        pq.emplace(-dist[x][y][0], x, y, 0);
      }
    } else {
      for(int j=0; j<4; ++j) {
        int newx = x + dx[j], newy = y + dy[j];
        if(valid(newx, newy)) {
          if(dist[newx][newy][0]>cost+C) { //run
            dist[newx][newy][0] = cost+C;
            pq.emplace(-cost-C, newx, newy, 0);
          }
          if(dist[newx][newy][j+1]>cost+B) { //kick
            dist[newx][newy][j+1] = cost+B;
            pq.emplace(-cost-B, newx, newy, j+1);
          }
        }
      }
    }
  }

  long long ans = INF;
  for(int k=0; k<5; ++k) {
    ans = min(ans, dist[oneandn[1].first][oneandn[1].second][k]);
  }
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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