Submission #51111

#	Time	Username	Problem	Language	Result	Execution time	Memory
51111		Diuven	Soccer (JOI17_soccer)	C++11	100 / 100	754 ms	108736 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MX=510, inf=2e9;

const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};

int h, w;
ll a, b, c;
int dist[MX][MX];
int st, ed;

inline int f(int x, int y){
    return x*(w+1)+y;
}
inline bool valid(int x, int y){
    return 0<=x && x<=h && 0<=y && y<=w;
}

void init(){
    for(int x=0; x<=h; x++)
        for(int y=0; y<=w; y++)
            dist[x][y]=inf;

    queue<pii> Q;
    int n, x, y;
    cin>>n;

    for(int i=1; i<=n; i++){
        cin>>x>>y;
        dist[x][y]=0;
        Q.push({x,y});
        if(i==1) st=f(x,y);
        if(i==n) ed=f(x,y);
    }
    while(!Q.empty()){
        int x,y; tie(x,y)=Q.front(); Q.pop();
        for(int k=0; k<4; k++){
            int z=x+dx[k], w=y+dy[k];
            if(!valid(z,w) || dist[z][w]<inf) continue;
            dist[z][w]=dist[x][y]+1;
            Q.push({z,w});
        }
    }
}

struct edge {
    int to; ll cost;
    bool operator < (const edge &e) const {
        return cost>e.cost;
    }
};

ll ans[MX*MX*3];
vector<edge> G[MX*MX*3]; // ground, _, |

ll solve(){
    int S=(h+1)*(w+1), S2=S+S;
    fill(ans, ans+3*S+1, inf*1e7);
    for(int x=0; x<=h; x++){
        for(int y=0; y<=w; y++){
            int v=f(x,y);
            G[v].push_back({v+S, b});
            G[v].push_back({v+S2, b});
            
            G[v+S].push_back({v, dist[x][y]*c});

            G[v+S2].push_back({v, dist[x][y]*c});

            for(int k=0; k<4; k++){
                int w=x+dx[k], z=y+dy[k], u=f(w,z);
                if(!valid(w,z)) continue;
                G[v].push_back({u, c});
                if(k%2==0) G[v+S2].push_back({u+S2, a});
                else G[v+S].push_back({u+S, a});
            }
        }
    }
    
    priority_queue<edge> Q;
    Q.push({st, 0}); ans[st]=0;
    while(!Q.empty()){
        int v=Q.top().to; ll d=Q.top().cost; Q.pop();
        if(ans[v]!=d) continue;
        for(edge &e: G[v]){
            int x=e.to; ll c=e.cost;
            if(ans[x]<=c+d) continue;
            ans[x]=c+d;
            Q.push({x,ans[x]});
        }
    }
    return ans[ed];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>h>>w>>a>>b>>c;
    init();
    cout<<solve();
    return 0;
}

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