Submission #83013

#	Time	Username	Problem	Language	Result	Execution time	Memory
83013		Bodo171	Soccer (JOI17_soccer)	C++14	100 / 100	378 ms	23252 KiB

soccer

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
const int nmax=505;
const long long lim=1LL*1e18;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
struct node
{
    long long dd;
    int l,c,st;
};
struct cmp
{
    bool operator()(node unu,node doi)
    {
        return unu.dd>doi.dd;
    }
};
priority_queue< node,vector<node>,cmp> pq;
long long d[nmax][nmax][5];
long long D[nmax][nmax];
bool ok[nmax][nmax];
int n,m,li,ci,si,l1,l2,c1,c2,dir,nr,i,x,y,j,s;
long long di,A,B,C,ans;
void prp(int lf,int cf,int sf,long long df)
{
    if(lf<=0||cf<=0||lf>n||cf>m) return;
    if(df<d[lf][cf][sf])
    {
        d[lf][cf][sf]=df;
        pq.push({df,lf,cf,sf});
    }
}
void dij()
{
    while(!pq.empty())
    {
        li=pq.top().l;ci=pq.top().c;si=pq.top().st;di=pq.top().dd;
        pq.pop();
        if(li==l2&&ci==c2)
        {
            ans=di;
            return;
        }
        if(si==4)
        {
            for(dir=0;dir<4;dir++)
            {
                prp(li,ci,dir,di+1LL*B);
                prp(li+d1[dir],ci+d2[dir],si,di+1LL*C);
            }
        }
        else
        {
            prp(li+d1[si],ci+d2[si],si,di+1LL*A);
            prp(li,ci,4,di+1LL*D[li][ci]*C);
        }
    }
}
queue< pair<int,int> > q;
void prcD()
{
    int lf,cf;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(ok[i][j])
           {
               D[i][j]=1;
               q.push({i,j});
           }
    while(!q.empty())
    {
        li=q.front().first;ci=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            lf=li+d1[i];cf=ci+d2[i];
            if(lf>0&&lf<=n&&cf>0&&cf<=m&&(!D[lf][cf]))
            {
                D[lf][cf]=D[li][ci]+1;
                q.push({lf,cf});
            }
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          D[i][j]--;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    cin>>A>>B>>C;
    cin>>nr;
    n++,m++;
    for(i=1;i<=nr;i++)
    {
        cin>>x>>y;x++,y++;
        if(i<nr)
            ok[x][y]=1;
        if(i==1)
        {
            l1=x;c1=y;
        }
        if(i==nr)
        {
            l2=x;c2=y;
        }
    }
    prcD();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
           for(s=0;s<5;s++)
             d[i][j][s]=lim;
    d[l1][c1][4]=0;
    pq.push({0,l1,c1,4});
    dij();
    cout<<ans;
    return 0;
}

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