Submission #153269

#	Time	Username	Problem	Language	Result	Execution time	Memory
153269		arnold518	Soccer (JOI17_soccer)	C++14	100 / 100	1268 ms	61868 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXH = 500;
const ll INF = 1e18;

struct Point { int y, x; };

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

int H, W, N;
ll A, B, C, ans;
Point S[MAXN+10];

struct Queue
{
    int y, x, t; ll w;
    bool operator < (const Queue &p) const { return w>p.w; }
};
ll close[MAXH+10][MAXH+10];
ll dist[MAXH+10][MAXH+10][5];

int main()
{
    int i, j, k;

    scanf("%d%d%lld%lld%lld%d", &H, &W, &A, &B, &C, &N);
    for(i=1; i<=N; i++) scanf("%d%d", &S[i].y, &S[i].x);

    for(i=0; i<=H; i++) for(j=0; j<=W; j++) close[i][j]=INF;
    priority_queue<Queue> PQ;
    for(i=1; i<=N; i++) PQ.push({S[i].y, S[i].x, -1, 0});
    while(!PQ.empty())
    {
        Queue T=PQ.top(); PQ.pop();
        if(close[T.y][T.x]<=T.w) continue;
        close[T.y][T.x]=T.w;

        for(i=0; i<4; i++)
        {
            int ny=T.y+dy[i], nx=T.x+dx[i];
            if(0<=ny && ny<=H && 0<=nx && nx<=W) PQ.push({ny, nx, -1, T.w+C});
        }
    }

    for(i=0; i<=H; i++) for(j=0; j<=W; j++) for(k=0; k<5; k++) dist[i][j][k]=INF;
    PQ.push({S[1].y, S[1].x, 4, 0});
    while(!PQ.empty())
    {
        Queue T=PQ.top(); PQ.pop();
        if(dist[T.y][T.x][T.t]<=T.w) continue;
        dist[T.y][T.x][T.t]=T.w;

        if(T.t<4)
        {
            PQ.push({T.y, T.x, 4, T.w});
            int ny=T.y+dy[T.t], nx=T.x+dx[T.t];
            if(0<=ny && ny<=H && 0<=nx && nx<=W) PQ.push({ny, nx, T.t, T.w+A});
        }
        else
        {
            for(i=0; i<4; i++) PQ.push({T.y, T.x, i, T.w+close[T.y][T.x]+B});
            for(i=0; i<4; i++)
            {
                int ny=T.y+dy[i], nx=T.x+dx[i];
                if(0<=ny && ny<=H && 0<=nx && nx<=W) PQ.push({ny, nx, 4, T.w+C});
            }
        }
    }

    printf("%lld", min({dist[S[N].y][S[N].x][0], dist[S[N].y][S[N].x][1], dist[S[N].y][S[N].x][2], dist[S[N].y][S[N].x][3], dist[S[N].y][S[N].x][4]}));
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%lld%lld%lld%d", &H, &W, &A, &B, &C, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:34:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d%d", &S[i].y, &S[i].x);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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