Submission #650055

#	Time	Username	Problem	Language	Result	Execution time	Memory
650055		ToroTN	Toll (BOI17_toll)	C++14	100 / 100	196 ms	125896 KiB

toll

#include<bits/stdc++.h>
using namespace std;
int num,n,m,t,u_i,v_i,w_i,x,y,dp[5][5][50005][25],mx,pow_2[25],st,ed,val[5],nxt[5],ans;
void listdp()
{
    for(int i=0;i<=20;i++)
    {
        printf("%d\n",i);
        for(int j=0;j<=mx;j++)
        {
            for(int k=0;k<num;k++)
            {
                for(int l=0;l<num;l++)
                {
                    printf("%d %d %d %d\n",j,k,l,dp[k][l][j][i]);
                }
            }
        }
        printf("\n");
    }
}
int main()
{
    pow_2[0]=1;
    for(int i=1;i<=20;i++)pow_2[i]=pow_2[i-1]*2;
    for(int i=0;i<=4;i++)
    {
        for(int j=0;j<=4;j++)
        {
            for(int k=0;k<=50000;k++)
            {
                for(int l=0;l<=20;l++)
                {
                    dp[i][j][k][l]=1e9;
                }
            }
        }
    }
    scanf("%d%d%d%d",&num,&n,&m,&t);
    mx=(n-1)/num;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u_i,&v_i,&w_i);
        dp[u_i%num][v_i%num][u_i/num][0]=w_i;
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=mx;j++)
        {
            for(int k=0;k<num;k++)
            {
                for(int l=0;l<num;l++)
                {
                    for(int c=0;c<num;c++)
                    {
                        if(j+pow_2[i-1]<=mx)
                        {
                            dp[k][l][j][i]=min(dp[k][l][j][i],dp[k][c][j][i-1]+dp[c][l][j+pow_2[i-1]][i-1]);
                        }
                    }
                }
            }
        }
    }
    //listdp();
    while(t--)
    {
        scanf("%d%d",&x,&y);
        st=x/num;
        ed=y/num;
        x%=num;
        y%=num;
        if(st==ed)
        {
            if(x==y)
            {
                printf("0\n");
            }else
            {
                printf("-1\n");
            }
            continue;
        }
        for(int i=0;i<num;i++)val[i]=1e9;
        val[x]=0;
        for(int i=20;i>=0;i--)
        {
            if(st+pow_2[i]<ed)
            {
                for(int j=0;j<num;j++)
                {
                    nxt[j]=1e9;
                }
                for(int j=0;j<num;j++)
                {
                    for(int k=0;k<num;k++)
                    {
                        nxt[j]=min(nxt[j],val[k]+dp[k][j][st][i]);
                    }
                }
                st+=pow_2[i];
                for(int j=0;j<num;j++)
                {
                    val[j]=nxt[j];
                }
            }
        }
        ans=1e9;
        for(int i=0;i<num;i++)
        {
            ans=min(ans,val[i]+dp[i][y][ed-1][0]);
        }
        if(ans==1e9)
        {
            printf("-1\n");
        }else
        {
            printf("%d\n",ans);
        }
    }
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d%d%d%d",&num,&n,&m,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d%d",&u_i,&v_i,&w_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44