Submission #169141

#	Time	Username	Problem	Language	Result	Execution time	Memory
169141		combi1k1	Soccer (JOI17_soccer)	C++14	100 / 100	1170 ms	128632 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

#define all(x)  x.begin(),x.end()
#define sz(x)   (int)x.size()

#define pb      emplace_back
#define endl    "\n"

const ll    inf = 1e18;
const int   N   = 505;

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

typedef pair<ll,int>    ii;

vector<ii>  g[N * N * 5];

int d[N][N];
int S, T;

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int H, W;   cin >> H >> W;
    int A, B;   cin >> A >> B;
    int C;      cin >> C;

    H++;
    W++;

    for(int i = 0 ; i < H ; ++i)
    for(int j = 0 ; j < W ; ++j)
        d[i][j] = -1;

    int n;  cin >> n;

    queue<ii>   qu;

    for(int i = 0 ; i < n ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        d[x][y] = 0;

        qu.push(ii(x,y));

        if (i == 0)     S = (x * W + y) * 5 + 4;
        if (i == n - 1) T = (x * W + y) * 5 + 4;
    }

    while (qu.size())   {
        int x = qu.front().X;
        int y = qu.front().Y;   qu.pop();

        for(int i = 0 ; i < 4 ; ++i)    {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if (xx < 0 || xx >= H)  continue;
            if (yy < 0 || yy >= W)  continue;

            if (d[xx][yy] < 0)  {
                d[xx][yy] = d[x][y] + 1;
                qu.push(ii(xx,yy));
            }
        }
    }

    for(int i = 0 ; i < H ; ++i)
    for(int j = 0 ; j < W ; ++j)
        for(int k = 0 ; k < 4 ; ++k)    {
            int x = i + dx[k];
            int y = j + dy[k];

            int u = (i * W + j) * 5;
            int v = (x * W + y) * 5;

            g[u + k].pb(1ll * C * d[i][j] + B,u + 4);

            if (x < 0 || x >= H)    continue;
            if (y < 0 || y >= W)    continue;

            g[u + 4].pb(C,v + 4);
            g[u + k].pb(A,v + k);
            g[u + 4].pb(A,v + k);
        }

    vector<ll>  dis(H * W * 5 + 5,inf);

    priority_queue<ii,vector<ii>,greater<ii> >  pq;

    pq.push(ii(0,S));   dis[S] = 0;

    while (pq.size())   {
        int u  = pq.top().Y;
        ll  du = pq.top().X;

        pq.pop();

        if (du != dis[u])
            continue;

        for(ii  e : g[u])   {
            int v = e.Y;
            ll  C = e.X;

            if (dis[v] > du + C)    {
                dis[v] = du + C;

                pq.push(ii(dis[v],v));
            }
        }
    }

    cout << dis[T] << endl;
}
/*
6 5
1 3 6
3
1 1
0 4
6 5
*/

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