Submission #1308944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308944		wangzhiyi33	Soccer (JOI17_soccer)	C++20	100 / 100	475 ms	173260 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fir first
#define sec second
#define pb push_back

int n,m,a,b,c;
int bfs[502][502],dist[502][502][3];
int dx[4]={1,-1,0,0}; 
int dy[4]={0,0,1,-1};

int ins(int x,int y){
    return (x>=0 && y>=0 && x<=n && y<=m);
}

vector<array<int,4> >adj[502][502][3];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>a>>b>>c;
    for(int q=0;q<=n;q++){
        for(int w=0;w<=m;w++){
            bfs[q][w]=1e18;
        }
    }

    queue<pair<int,int>>qu;
    int pl; cin>>pl;
    vector<pair<int,int> >apa;
    apa.pb({0,0});

    for(int q=1;q<=pl;q++){
        int x,y; cin>>x>>y;
        apa.pb({x,y});
        qu.push({x,y}); bfs[x][y]=0;
    }

    while(qu.size()){
        auto [x,y]=qu.front(); qu.pop();
        for(int q=0;q<4;q++){
            int nx=x+dx[q],ny=y+dy[q];
            if(ins(nx,ny) && bfs[nx][ny]>bfs[x][y]+1){
                bfs[nx][ny]=bfs[x][y]+1;
                qu.push({nx,ny});
            }
        }
    }   

    for(int q=0;q<=n;q++){
        for(int w=0;w<=m;w++){
            dist[q][w][0]=dist[q][w][1]=dist[q][w][2]=1e18;

            // type 0 : jalan sama bola
            adj[q][w][0].pb({q,w,1,b});
            adj[q][w][0].pb({q,w,2,b});

            for(int e=0;e<4;e++){
                int nx=q+dx[e],ny=w+dy[e];
                if(!ins(nx,ny))continue;
                adj[q][w][0].pb({nx,ny,0,c});
            }

            // type 1 : jalan sesuai row
            for(int e=0;e<2;e++){
                int nx=q+dx[e],ny=w+dy[e];
                if(!ins(nx,ny))continue;
                adj[q][w][1].pb({nx,ny,1,a});
            }
            adj[q][w][1].pb({q,w,0,bfs[q][w]*c});

            // type 2 : jalan sesuai column
            for(int e=2;e<4;e++){
                int nx=q+dx[e],ny=w+dy[e];
                if(!ins(nx,ny))continue;
                adj[q][w][2].pb({nx,ny,2,a});
            }
            adj[q][w][2].pb({q,w,0,bfs[q][w]*c});
        }
    }

    priority_queue<array<int,4>,vector<array<int,4> >,greater<array<int,4> > >pq;
    dist[apa[1].fir][apa[1].sec][0]=0; pq.push({0,apa[1].fir,apa[1].sec,0});

    while(pq.size()){
        auto [jrk,x,y,ty]=pq.top(); pq.pop();
        if(dist[x][y][ty]!=jrk)continue;

        for(auto [nx,ny,nty,cost] : adj[x][y][ty]){
            if(dist[nx][ny][nty]>jrk+cost){
                dist[nx][ny][nty]=jrk+cost;
                pq.push({dist[nx][ny][nty],nx,ny,nty});
            }
        }
    }

    int ans=min({dist[apa[pl].fir][apa[pl].sec][0], dist[apa[pl].fir][apa[pl].sec][1], dist[apa[pl].fir][apa[pl].sec][2]});
    cout<<ans<<endl;

}

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