제출 #1247967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247967		minhpk	Soccer (JOI17_soccer)	C++20	100 / 100	227 ms	22904 KiB

soccer

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int A,B,C;
int n;
pair<int,int> z[1000005];

bool vis[505][505];
pair<int,int> pos[505][505];
int cnt[505][505];
int hx[4]={1,-1,0,0};
int hy[4]={0,0,-1,1};
int dp[505][505][3];

int bruh=1e16;
void bfs(){
     queue<pair<int,int>> q;
     for (int i=1;i<n;i++){
          q.push({z[i].first,z[i].second});
          pos[z[i].first][z[i].second]={z[i].first,z[i].second};
          cnt[z[i].first][z[i].second]=0;
          vis[z[i].first][z[i].second]=true;
     }
     while (q.size()){
          auto [x,y]=q.front();
          q.pop();
          for (int k=0;k<4;k++){
               int dx=x+hx[k];
               int dy=y+hy[k];
               if (dx<0 || dy<0 || dx>a || dy>b){
                   continue;
               }
               if (vis[dx][dy]==true){
                   continue;
               }
               cnt[dx][dy]=cnt[x][y]+1;
               vis[dx][dy]=true;
               pos[dx][dy]={x,y};
               q.push({dx,dy});
          }
     }
}


void dijkstra(){
    for (int i=0;i<=a;i++){
         for (int j=0;j<=b;j++){
              for (int k=0;k<=2;k++){
                  dp[i][j][k]=bruh;
              }
         }
    }
    priority_queue<pair<pair<int,int>,pair<int,int>> ,vector<pair<pair<int,int>,pair<int,int>>> ,greater<pair<pair<int,int>,pair<int,int>>> > q;
    q.push({{0,2},{z[1].first,z[1].second}});
    dp[z[1].first][z[1].second][2]=0;
    while (q.size()){
         pair<pair<int,int>,pair<int,int>>pos=q.top();
         q.pop();
         int val=pos.first.first;
         int t=pos.first.second;
         int x=pos.second.first;
         int y=pos.second.second;
         if (val>dp[x][y][t]){
             continue;
         }
         if (t==2){
             for (int k=0;k<4;k++){
                 int dx=x+hx[k];
                 int dy=y+hy[k];
                 if (dx<0 || dy<0 || dx>a || dy>b){
                     continue;
                 }
                 if (dp[dx][dy][2]>val+C){
                     dp[dx][dy][2]=val+C;
                     q.push({{dp[dx][dy][2],2},{dx,dy}});
                 }
             }
             if (dp[x][y][0]>val+B){
                 dp[x][y][0]=val+B;
                 q.push({{dp[x][y][0],0},{x,y}});
             }
             if (dp[x][y][1]>val+B){
                 dp[x][y][1]=val+B;
                 q.push({{dp[x][y][1],1},{x,y}});
             }
         }else{
             if (t==0){
                 for (int k=0;k<2;k++){
                     int dx=x+hx[k];
                     int dy=y+hy[k];
                     if (dx<0 || dy<0 || dx>a || dy>b){
                         continue;
                     }
                     if (dp[dx][dy][0]>val+A){
                         dp[dx][dy][0]=val+A;
                         q.push({{dp[dx][dy][0],0},{dx,dy}});
                     }
                 }
             }else{
                 for (int k=2;k<4;k++){
                     int dx=x+hx[k];
                     int dy=y+hy[k];
                     if (dx<0 || dy<0 || dx>a || dy>b){
                         continue;
                     }
                     if (dp[dx][dy][1]>val+A){
                         dp[dx][dy][1]=val+A;
                         q.push({{dp[dx][dy][1],1},{dx,dy}});
                     }
                 }
             }

             if (dp[x][y][2]>val+cnt[x][y]*C){
                 dp[x][y][2]=val+cnt[x][y]*C;
                 q.push({{dp[x][y][2],2},{x,y}});
             }
         }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    cin >> A >> B >> C;
    cin >> n;
    for (int i=1;i<=n;i++){
         cin >> z[i].first >> z[i].second;
    }
    bfs();
    dijkstra();
    auto [x,y]=z[n];
    cout << min({dp[x][y][0],dp[x][y][1],dp[x][y][2]}) << "\n";
    return 0;
}

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