Submission #263724

#	Time	Username	Problem	Language	Result	Execution time	Memory
263724		daniel920712	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	53 ms	11644 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;
    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++)
    {
        //printf("%lld %lld\n",in[i],out[i]);
        con[i][i]=1e18;
        for(j=1;j<=N;j++)
        {
            //printf("%lld %lld %lld\n",i,j,con[i][j]);
            P[i][j]=0;
            if(con[i][j]>=0) Q[i][j]=con[i][j];
            else Q[i][j]=1e18;

            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]&&(double) (S[j][k]-B[i][k])/(double) con[i][j]>(double) P[i][j]/(double) Q[i][j])
                {
                    P[i][j]=(S[j][k]-B[i][k]);
                    Q[i][j]=con[i][j];
                }
            }
            //printf("%lld %lld %lld %lld\n",i,j,P[i][j],Q[i][j]);
        }
    }
    ok=1;
    while(ok)
    {
        ok=0;
        for(k=1;k<=N;k++)
        {
            for(i=1;i<=N;i++)
            {
                for(j=1;j<=N;j++)
                {
                    if(i==k||k==j) continue;
                    if(con[i][k]==-1||con[k][j]==-1||con[i][j]==-1||(Q[i][k]+Q[k][j])==0) continue;
                    if(Q[i][j]==0||(double) (P[i][k]+P[k][j])/(double) (Q[i][k]+Q[k][j])>(double) P[i][j]/(double) Q[i][j])
                    {
                        P[i][j]=(P[i][k]+P[k][j]);
                        Q[i][j]=(Q[i][k]+Q[k][j]);
                        //printf("%lld %lld %lld %lld %lld %lld %lld\n",i,j,k,P[i][k],P[k][j],Q[i][k],Q[k][j]);
                        //ok=1;
                    }
                }
            }
        }
    }

    for(i=1;i<=N;i++)
    {
        //printf("%lld %lld\n",P[i][i],Q[i][i]);
        if(Q[i][i]) ans=max(ans,P[i][i]/Q[i][i]);
    }
    printf("%lld\n",ans);



    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
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