Submission #263816

#	Time	Username	Problem	Language	Result	Execution time	Memory
263816		daniel920712	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	115 ms	11896 KiB

merchant

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
vector < pair < long long , long long > > Next[200005];
vector < pair < long long , long long > > last[200005];
long long S[105][1005];
long long B[105][1005];
long long con[105][105];
bool have[105];
long long P[105][105];
long long Q[105][105];
priority_queue < pair < long long , long long > , vector < pair < long long , long long > > , greater < pair < long long , long long > > > all;
int main()
{
    long long N,M,K,a,b,c,ans=0,i,j,k,ok,l,r;
    scanf("%lld %lld %lld",&N,&M,&K);
    for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]);
    while(M--)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        Next[a].push_back(make_pair(b,c));
    }

    for(j=1;j<=N;j++)
    {
        for(i=1;i<=N;i++)
        {
            P[j][i]=0;
            Q[j][i]=1;
            con[j][i]=-1;
            have[i]=0;
        }
        all.push(make_pair(0,j));
        while(!all.empty())
        {
            if(have[all.top().second])
            {
                all.pop();
                continue;
            }
            have[all.top().second]=1;
            con[j][all.top().second]=all.top().first;
            for(auto i:Next[all.top().second]) all.push(make_pair(all.top().first+i.second,i.first));
            all.pop();
        }

    }
    for(i=1;i<=N;i++)
    {
        con[i][i]=0;
        for(j=1;j<=N;j++)
        {
            P[i][j]=0;
            Q[i][j]=con[i][j];
            for(k=1;k<=K;k++)
            {
                if(con[i][j]!=-1&&S[j][k]!=-1&&B[i][k]!=-1&&S[j][k]>B[i][k])
                {
                    P[i][j]=max(P[i][j],(S[j][k]-B[i][k]));
                    Q[i][j]=con[i][j];
                }
            }
        }
    }
    l=0;
    r=1e18;
    ok=1;
    while((r-l)>1)
    {
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=N;j++)
            {
                if(i==j) Q[i][j]=0;
                else if(con[i][j]==-1) Q[i][j]=-1;
                else Q[i][j]=con[i][j]*((l+r)/2)-P[i][j];

            }
        }

        for(k=1;k<=N;k++)
        {
            for(i=1;i<=N;i++)
            {
                for(j=1;j<=N;j++)
                {
                    Q[i][j]=min(Q[i][j],Q[i][k]+Q[k][j]);
                }
            }
        }
        ok=0;
        for(i=1;i<=N;i++)
        {
            if(Q[i][i]<0) ok=1;
        }
        if(ok) l=(l+r)/2;
        else r=(l+r)/2;
    }


    printf("%lld\n",r);



    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:23:27: warning: unused variable 'ans' [-Wunused-variable]
   23 |     long long N,M,K,a,b,c,ans=0,i,j,k,ok,l,r;
      |                           ^~~
merchant.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%lld %lld %lld",&N,&M,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:25:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]);
      |                                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         scanf("%lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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