Submission #647627

#	Time	Username	Problem	Language	Result	Execution time	Memory
647627		ToroTN	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	103 ms	2140 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,num,b[105][1005],s[105][1005],u_i,v_i,w_i,d[105][105],profit[105][105],dis[105][105],type;
int main()
{
    scanf("%lld%lld%lld",&n,&m,&num);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=num;j++)
        {
            scanf("%lld%lld",&b[i][j],&s[i][j]);
        }
        for(int j=1;j<=n;j++)d[i][j]=1e18;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&u_i,&v_i,&w_i);
        d[u_i][v_i]=w_i;
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=num;k++)
            {
                if(b[i][k]!=-1&&s[j][k]!=-1)
                {
                    profit[i][j]=max(profit[i][j],s[j][k]-b[i][k]);
                }
            }
        }
    }
    ll st=1,md,ed=1e9;
    while(ed>=st)
    {
        md=(st+ed)/2;
        //printf("%lld %lld %lld\n",st,md,ed);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //////
                /*if(d[i][j]>1e18/md)
                {
                    dis[i][j]=1e18;
                }else
                {
                    dis[i][j]=d[i][j]*md-profit[i][j];
                }*/
                ///////
                dis[i][j]=md*min(d[i][j],(ll)1e18/md)-profit[i][j];
                //printf("%lld ",dis[i][j]);
            }
            //printf("\n");
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                }
            }
        }
        type=-1;
        for(int i=1;i<=n;i++)
        {
            if(dis[i][i]<=0)
            {
                type=0;
            }
        }
        if(type==0)
        {
            st=md+1;
        }else
        {
            ed=md-1;
        }
    }
    //printf("%lld %lld %lld\n",st,md,ed);
    printf("%lld",ed);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%lld%lld%lld",&n,&m,&num);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:12:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             scanf("%lld%lld",&b[i][j],&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%lld%lld%lld",&u_i,&v_i,&w_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34