Submission #907562

#	Time	Username	Problem	Language	Result	Execution time	Memory
907562		andrei_iorgulescu	Soccer (JOI17_soccer)	C++14	100 / 100	1106 ms	48496 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;
int dl[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};

struct stare
{
    int i,j,q;
};

int h,w,a,b,c,n;
pair<int,int>p[100005];
int d[505][505][5];
bool om[505][505];
int dmin[505][505];

class Compare
{
public:
    bool operator()(pair<int,stare>cine1, pair<int,stare>cine2)
    {
        return cine1.first < cine2.first;
    }
};

void calc_dmin()
{
    for (int i = 0; i <= h; i++)
        for (int j = 0; j <= w; j++)
            dmin[i][j] = inf;
    queue<pair<int,int>> qq;
    for (int i = 1; i <= n; i++)
    {
        qq.push(p[i]);
        dmin[p[i].first][p[i].second] = 0;
    }
    while (!qq.empty())
    {
        pair<int,int> nod = qq.front();
        qq.pop();
        for (int i = 0; i < 4; i++)
        {
            int l = nod.first + dl[i],c = nod.second + dc[i];
            if (l >= 0 and l <= h and c >= 0 and c <= w and dmin[l][c] == inf)
            {
                dmin[l][c] = 1 + dmin[nod.first][nod.second];
                qq.push({l,c});
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> h >> w >> a >> b >> c >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second,om[p[i].first][p[i].second] = true;
    calc_dmin();
    for (int i = 0; i <= h; i++)
    {
        for (int j = 0; j <= w; j++)
        {
            for (int q = 0; q < 5; q++)
                d[i][j][q] = inf;
        }
    }
    priority_queue<pair<int,stare>, vector<pair<int,stare>>, Compare>pq;
    stare initial;
    initial.i = p[1].first;
    initial.j = p[1].second;
    initial.q = 0;
    pq.push({0,initial});
    while (!pq.empty())
    {
        int timp = -pq.top().first;
        stare nod = pq.top().second;
        //cout << timp << ' ' << nod.i << ' ' << nod.j << ' ' << nod.q << endl;
        pq.pop();
        if (d[nod.i][nod.j][nod.q] == inf)
        {
            d[nod.i][nod.j][nod.q] = timp;
            if (nod.q == 0)
            {
                stare vecin;
                vecin.i = nod.i;
                vecin.j = nod.j;
                for (vecin.q = 1; vecin.q <= 4; vecin.q++)
                    pq.push({-(timp + b),vecin});
                vecin.q = 0;
                for (int cv = 0; cv < 4; cv++)
                {
                    vecin.i = nod.i + dl[cv];
                    vecin.j = nod.j + dc[cv];
                    if (vecin.i >= 0 and vecin.i <= h and vecin.j >= 0 and vecin.j <= w)
                        pq.push({-(timp + c),vecin});
                }
            }
            else
            {
                stare vecin;
                vecin.i = nod.i;
                vecin.j = nod.j;
                vecin.q = 0;
                pq.push({-(timp + c * dmin[nod.i][nod.j]),vecin});
                vecin.q = nod.q;
                vecin.i = nod.i + dl[nod.q - 1];
                vecin.j = nod.j + dc[nod.q - 1];
                if (vecin.i >= 0 and vecin.i <= h and vecin.j >= 0 and vecin.j <= w)
                    pq.push({-(timp + a),vecin});
            }
        }
    }
    cout << d[p[n].first][p[n].second][0];
    /*for (int i = 0; i <= 6; i++)
    {
        for (int j = 0; j <= 5; j++)
        {
            for (int q = 0; q <= 4; q++)
                cout << i << ' ' << j << ' ' << q << ' ' << d[i][j][q] << endl;
        }
    }*/
    return 0;
}

/**
d[i][j][0/1/2/3/4] = costul minim ca mingea sa fie la pozitia i si fie sa stea la un om (0) fie sa aiba momentum in dir 1/2/3/4
calculez d cu un dijkstra
din starea (i,j,0) ma pot duce in starea (i,j,1/2/3/4) cu cost B
din starea (i,j,dir) ma pot duce in starea (i_vec,j_vec,dir) cu cost A unde (i_vec,j_vec) e vecina pe directia dir cu (i,j)
din starea (i,j,dir) ma pot duce in starea (i,j,0) cu cost 0 doar daca am om in pozitia (i,j)
din starea (i,j,0) ma pot duce in starea (i_vec,j_vec,0) cu cost C unde (i_vec,j_vec) este vecin pe orice directie cu (i,j)
raspunsul meu este d[sN][tN][0]
initial pornesc cu d[s1][t1][0] = 0
**/

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