Submission #738401

#	Time	Username	Problem	Language	Result	Execution time	Memory
738401		1075508020060209tc	Soccer (JOI17_soccer)	C++14	0 / 100	834 ms	54172 KiB

soccer

#include<bits/stdc++.h>

using namespace std;
#define int long long
int H;int W;
int n;
int A;int B;int C;
int dir[5]={0,1,0,-1,0};
pair<int,int>ar[500005];
int mht[510][510];
int ok(int x,int y){
if(x>=1&&x<=H&&y>=1&&y<=W){return 1;}
return 0;
}
void mhtcalc(){
for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
        mht[i][j]=-1;
    }
}
queue<pair<int,int>>q;
for(int i=1;i<=n;i++){
    mht[ar[i].first][ar[i].second]=0;
    q.push(ar[i]);
}
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    for(int i=0;i<4;i++){
        int x=nwx+dir[i];int y=nwy+dir[i+1];
        if(!ok(x,y)){continue;}
        if(mht[x][y]==-1){
            mht[x][y]=mht[nwx][nwy]+1;
            q.push({x,y});
        }
    }
}
}
int dis[5][510][510];
int vis[5][510][510];


signed main(){
cin>>H>>W;
cin>>A>>B>>C;
cin>>n;
for(int i=1;i<=n;i++){
    cin>>ar[i].first>>ar[i].second;
}
mhtcalc();

for(int i=0;i<=4;i++){
    for(int a=1;a<=H;a++){
        for(int b=1;b<=W;b++){
            dis[i][a][b]=1e18;
        }
    }
}
priority_queue<pair<int,array<int,3>>,vector<pair<int,array<int,3>>>,greater<pair<int,array<int,3>>>>pq;
dis[0][ar[1].first][ar[1].second]=0;
pq.push({0,{0,ar[1].first,ar[1].second}});

while(pq.size()){
    int nwd=pq.top().second[0];
    int nwx=pq.top().second[1];
    int nwy=pq.top().second[2];
    pq.pop();
    if(vis[nwd][nwx][nwy]){continue;}
    vis[nwd][nwx][nwy]=1;
    if(nwd==0){
        for(int i=0;i<4;i++){
            int x=nwx+dir[i];int y=nwy+dir[i+1];
            if(!ok(x,y)){continue;}
            if(vis[0][x][y]){continue;}
            dis[0][x][y]=min(dis[0][x][y],dis[0][nwx][nwy]+C);
            pq.push({dis[0][x][y],{0,x,y}});
        }
        for(int i=1;i<=4;i++){
            int x=nwx+dir[i-1];int y=nwy+dir[i];
            if(!ok(x,y)){continue;}
            if(vis[i][x][y]){continue;}
            dis[i][x][y]=min(dis[i][x][y],dis[0][nwx][nwy]+A+B);
            pq.push({dis[i][x][y],{i,x,y}});
        }
        continue;
    }
    dis[0][nwx][nwy]=min(dis[0][nwx][nwy],dis[nwd][nwx][nwy]+mht[nwx][nwy]*C);
    pq.push({dis[0][nwx][nwy],{0,nwx,nwy}});
    int x=nwx+dir[nwd-1];int y=nwy+dir[nwd];
    if(ok(x,y)&&!vis[nwd][x][y]){
        dis[nwd][x][y]=min(dis[nwd][x][y],dis[nwd][nwx][nwy]+A);
        pq.push({dis[nwd][x][y],{nwd,x,y}});
    }
}
int ans=dis[0][ar[n].first][ar[n].second];
for(int i=1;i<=4;i++){
    ans=min(ans,dis[i][ar[n].first][ar[n].second]);
}
cout<<ans<<endl;

}

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