Submission #53655

#	Time	Username	Problem	Language	Result	Execution time	Memory
53655		SpaimaCarpatilor	Soccer (JOI17_soccer)	C++17	0 / 100	3067 ms	69572 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

int A, B, C, H, W, N, d[509][509], x[100009], y[100009];
long long minD[509][509];
const long long INF = 1LL << 60;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue < pair < int, int > > cc;

void read ()
{
    scanf ("%d %d", &H, &W), H ++, W ++;
    scanf ("%d %d %d", &A, &B, &C);
    scanf ("%d", &N);
    for (int i=1; i<=H; i++)
        for (int j=1; j<=W; j++)
            d[i][j] = -1;
    for (int i=1; i<=N; i++)
    {
        scanf ("%d %d", &x[i], &y[i]), x[i] ++, y[i] ++;
        d[x[i]][y[i]] = 0, cc.push ({x[i], y[i]});
    }
    while (!cc.empty ())
    {
        auto curr = cc.front ();
        cc.pop ();
        for (int k=0; k<4; k++)
        {
            int nx = curr.first + dx[k], ny = curr.second + dy[k];
            if (d[nx][ny] == -1)
                d[nx][ny] = d[curr.first][curr.second] + 1, cc.push ({nx, ny});
        }
    }
}

priority_queue < pair < long long, pair < int, int > > > PQ;
void update (int i, int j, long long d)
{
    if (i < 1 || j < 1 || i > H || j > W) return ;
    if (d < minD[i][j])
        minD[i][j] = d, PQ.push ({-d, {i, j}});
}

int modul (int x)
{
    if (x < 0) return -x;
    return x;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read ();
for (int i=1; i<=H; i++)
    for (int j=1; j<=W; j++)
        minD[i][j] = INF;
PQ.push ({0, {x[1], y[1]}}), minD[x[1]][y[1]] = 0;
while (!PQ.empty ())
{
    auto curr = PQ.top ();
    PQ.pop ();
    int i = curr.second.first, j = curr.second.second;
    if (minD[i][j] != -curr.first) continue;
    for (int k=0; k<4; k++)
        update (i + dx[k], j + dy[k], minD[i][j] + C);
    for (int l=1; l<=H; l++)
        update (l, j, minD[i][j] + 1LL * C * d[l][j] + B + 1LL * A * modul (l - i));
    for (int c=1; c<=W; c++)
        update (i, c, minD[i][j] + 1LL * C * d[i][c] + B + 1LL * A * modul (c - j));
}
printf ("%lld\n", minD[x[N]][y[N]]);
return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'void read()':
soccer.cpp:14:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &H, &W), H ++, W ++;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
soccer.cpp:15:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &A, &B, &C);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:16:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
soccer.cpp:22:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &x[i], &y[i]), x[i] ++, y[i] ++;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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