제출 #1352715

#제출 시각아이디문제언어결과실행 시간메모리
1352715WarinchaiSoccer (JOI17_soccer)C++20
100 / 100
1380 ms79428 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int can[505][505];
int dis[505][505][10];
int vis[505][505][10];
int idis[505][505];
int ivis[505][505];
pair<int,int>dir[4]={
    {1,0},{-1,0},{0,1},{0,-1}
};
int inf=1e18;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int h,w;cin>>h>>w;
    int a,b,c;cin>>a>>b>>c;
    int n;cin>>n;
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        v.push_back({x,y});
    }
    for(int i=0;i<=h;i++)for(int j=0;j<=w;j++)idis[i][j]=inf;
    queue<pair<int,int>>q;
    for(auto x:v)idis[x.first][x.second]=0,q.push({x.first,x.second});
    while(!q.empty()){
        auto [x,y]=q.front();
        q.pop();
        if(ivis[x][y])continue;
        ivis[x][y]=1;
        for(int i=0;i<4;i++){
            int xx=x+dir[i].first;
            int yy=y+dir[i].second;
            if(xx>=0&&xx<=h&&yy>=0&&yy<=w){
                if(idis[x][y]+1<idis[xx][yy]){
                    idis[xx][yy]=idis[x][y]+1;
                    q.push({xx,yy});
                }
            }
        }
    }
    for(int i=0;i<=h;i++)for(int j=0;j<=w;j++)for(int k=0;k<5;k++)dis[i][j][k]=inf;
    priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>>pq;
    pq.push(make_tuple(0,v[0].first,v[0].second,0));
    while(!pq.empty()){
        auto [d,x,y,t]=pq.top();
        pq.pop();
        if(vis[x][y][t])continue;
        vis[x][y][t]=1;
        dis[x][y][t]=d;
        //cerr<<x<<" "<<y<<" "<<t<<" "<<d<<"\n";
        if(t==0){
            for(int i=0;i<4;i++){
                int xx=x+dir[i].first;
                int yy=y+dir[i].second;
                if(xx>=0&&xx<=h&&yy>=0&&yy<=w)pq.push(make_tuple(d+c,xx,yy,0));
                pq.push(make_tuple(d+b,x,y,i+1));
            }
        }else{
            int xx=x+dir[t-1].first;
            int yy=y+dir[t-1].second;
            if(xx>=0&&xx<=h&&yy>=0&&yy<=w)pq.push(make_tuple(d+a,xx,yy,t));
            pq.push(make_tuple(d+idis[x][y]*c,x,y,0));
        }
    }
    int ans=inf;
    for(int i=0;i<5;i++)ans=min(ans,dis[v.back().first][v.back().second][i]);
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...