Submission #87929

#	Time	Username	Problem	Language	Result	Execution time	Memory
87929		tieunhi	Soccer (JOI17_soccer)	C++14	100 / 100	664 ms	26400 KiB

soccer

#include <bits/stdc++.h>
#define pii pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define N 505
#define MM 100005
#define LN 19
#define maxc 1000000007

using namespace std;

int n, m, A, B, C, k;
pii pp[MM];
ll dist[N][N], d[N][N][5];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void setup()
{
    cin >> n >> m >> A >> B >> C; n++; m++;
    cin >> k;
    FOR(i, 1, k)
    {
        int u, v; cin >> u >> v; u++; v++;
        pp[i] = mp(u, v);
    }
}
void prepare()
{
    FOR(i, 0, n+1)
        FOR(j, 0, m+1) dist[i][j] = (1ll << 60);
    queue<pii> q;
    FOR(i, 1, k)
    {
        dist[pp[i].F][pp[i].S] = 0;
        q.push(pp[i]);
    }
    while (!q.empty())
    {
        auto z = q.front(); q.pop();
        FOR(i, 1, 4)
        {
            int x = z.F + dx[i];
            int y = z.S + dy[i];
            if (x > 0 && y > 0 && x <= n && y <= m && dist[x][y] == (1ll << 60))
            {
                dist[x][y] = dist[z.F][z.S] + C;
                q.push(mp(x, y));
            }
        }
    }
}
void solve()
{
    priority_queue<pair<ll, pair<pii, int> > >q;
    FOR(i, 1, n)
        FOR(j, 1, m)
            FOR(k, 0, 4) d[i][j][k] = (1ll << 60);
    q.push(mp(0, mp(mp(pp[1].F, pp[1].S), 0)));
    d[pp[1].F][pp[1].S][0] = 0;
    while (!q.empty())
    {
        auto z = q.top(); q.pop();
        int u = z.S.F.F;
        int v = z.S.F.S;
        int dir = z.S.S;
        ll len = -z.F;
        if (d[u][v][dir] < len) continue;
        if (dir == 0)
        {
            FOR(i, 1, 4)
                if (d[u][v][i] > d[u][v][0] + B)
                {
                    d[u][v][i] = d[u][v][0] + B;
                    q.push(mp(-d[u][v][i], mp(mp(u, v), i)));
                }
            FOR(i, 1, 4)
            {
                int x = u + dx[i];
                int y = v + dy[i];
                if (d[x][y][0] > d[u][v][0] + C)
                {
                    d[x][y][0] = d[u][v][0] + C;
                    q.push(mp(-d[x][y][0], mp(mp(x, y), 0)));
                }
            }
        }
        else
        {
            if (d[u][v][0] > d[u][v][dir] + dist[u][v])
            {
                d[u][v][0] = d[u][v][dir] + dist[u][v];
                q.push(mp(-d[u][v][0], mp(mp(u, v), 0)));
            }
            int x = u + dx[dir];
            int y = v + dy[dir];
            if (d[x][y][dir] > d[u][v][dir] + A)
            {
                d[x][y][dir] = d[u][v][dir] + A;
                q.push(mp(-d[x][y][dir], mp(mp(x, y), dir)));
            }
        }
    }
    ll res = 1ll << 60;
    FOR(i, 0, 4) res = min(res, d[pp[k].F][pp[k].S][i]);
    cout <<res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    setup();
    prepare();
    solve();
}

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