Submission #205611

#	Time	Username	Problem	Language	Result	Execution time	Memory
205611		Kastanda	Soccer (JOI17_soccer)	C++11	100 / 100	537 ms	19076 KiB

soccer

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 505, MXN = 100005;
int n, m, k, A, B, C, P[N][N];
pair < int , int > At[MXN];
long long D[N][N][5];
int gx[] = {-1, 1, 0, 0};
int gy[] = {0, 0, -1, 1};
int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d", &A, &B, &C);
    scanf("%d", &k);
    memset(P, 63, sizeof(P));
    queue < pair < int , int > > qu;
    for (int i = 1; i <= k; i ++)
    {
        scanf("%d%d", &At[i].first, &At[i].second);
        P[At[i].first][At[i].second] = 0;
        if (i < k) qu.push({At[i].first, At[i].second});
    }
    while (qu.size())
    {
        int a = qu.front().first;
        int b = qu.front().second;
        qu.pop();
        for (int h = 0; h < 4; h ++)
        {
            int ta = a + gx[h];
            int tb = b + gy[h];
            if (ta >= 0 && ta <= n && tb >= 0 && tb <= m && P[ta][tb] > P[a][b] + 1)
                P[ta][tb] = P[a][b] + 1, qu.push({ta, tb});
        }
    }
    P[At[k].first][At[k].second] = 0;
    memset(D, 63, sizeof(D));
    priority_queue < tuple < long long , int , int , int > > Pq;
    auto Relax = [&] (int a, int b, int w, long long d) {
        if (D[a][b][w] > d) {
            D[a][b][w] = d;
            Pq.push(make_tuple(-d, a, b, w));
        }
    };
    Relax(At[1].first, At[1].second, 4, 0);
    while (Pq.size())
    {
        long long d;
        int a, b, w;
        tie(d, a, b, w) = Pq.top();
        Pq.pop(); d = -d;
        if (d > D[a][b][w])
            continue;
        if (w < 4)
        {
            int ta = a + gx[w], tb = b + gy[w];
            if (ta >= 0 && ta <= n && tb >= 0 && tb <= m)
                Relax(ta, tb, w, d + A);
            Relax(a, b, 4, d + 1LL * P[a][b] * C);
        }
        else
        {
            for (int h = 0; h < 4; h ++)
            {
                int ta = a + gx[h], tb = b + gy[h];
                if (ta >= 0 && ta <= n && tb >= 0 && tb <= m)
                    Relax(ta, tb, 4, d + C);
                Relax(a, b, h, d + B);
            }
        }
    }
    long long Mn = LLONG_MAX;
    for (int h = 0; h <= 4; h ++)
        Mn = min(Mn, D[At[k].first][At[k].second][h]);
    return !printf("%lld\n", Mn);
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:13:10: 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:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
soccer.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &At[i].first, &At[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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