Submission #348975

#	Time	Username	Problem	Language	Result	Execution time	Memory
348975		denkendoemeer	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	108 ms	4844 KiB

merchant

#include<bits/stdc++.h>
#define ll long long
const ll inf=1e18;
using namespace std;
int b[105][1005],s[105][1005],p[1005][1005];
ll dist[1005][1005],dp[1005][1005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,k,i,x,y,j,e;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)
        for(j=1;j<=k;j++)
            scanf("%d%d",&b[i][j],&s[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(e=1;e<=k;e++)
                if (b[i][e]!=-1 && s[j][e]!=-1)
                    p[i][j]=max(p[i][j],s[j][e]-b[i][e]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            dist[i][j]=inf;
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        scanf("%lld",&dist[x][y]);
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(e=1;e<=n;e++)
                dist[j][e]=min(dist[j][e],dist[j][i]+dist[i][e]);
    int st=1,dr=1e9,mij,ans=0;
    while(st<=dr){
        mij=(st+dr)/2;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                dp[i][j]=1LL*mij*min(dist[i][j],inf/mij)-p[i][j];
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                for(e=1;e<=n;e++)
                    dp[j][e]=min(dp[j][e],dp[j][i]+dp[i][e]);
        for(i=1;i<=n;i++)
            if (dp[i][i]<=0)
                break;
        if (i<=n)
            ans=mij,st=mij+1;
        else
            dr=mij-1;
    }
    printf("%d\n",ans);
return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |             scanf("%d%d",&b[i][j],&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
merchant.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         scanf("%lld",&dist[x][y]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

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