Submission #155116

#	Time	Username	Problem	Language	Result	Execution time	Memory
155116		mhy908	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	112 ms	4252 KiB

merchant

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define llinf 987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
int n, m, k;
LL buy[110][1010], sell[110][1010];
LL floyd[110][110];
LL cost[110][110];
LL edge[110][110];
bool negcycle()
{
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                edge[i][j]=min(edge[i][j], edge[i][k]+edge[k][j]);
            }
        }
    }
    bool ret=false;
    for(int i=1; i<=n; i++){
        if(edge[i][i]<=0)ret=true;
    }
    return ret;
}
LL binsearch(LL a, LL b){
    if(a==b)return a;
    LL mid=(a+b)/2+1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            edge[i][j]=min((LL)inf, mid*floyd[i][j]-cost[i][j]);
        }
    }
    if(negcycle())return binsearch(mid, b);
    return binsearch(a, mid-1);
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++)
            scanf("%lld %lld", &buy[i][j], &sell[i][j]);
    for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)floyd[i][j]=inf;
    for(int i=1; i<=m; i++){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        floyd[a][b]=min(floyd[a][b], c);
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                floyd[i][j]=min(floyd[i][j], floyd[i][k]+floyd[k][j]);
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int z=1; z<=k; z++){
                if(sell[j][z]>=0&&buy[i][z]>=0)cost[i][j]=max(cost[i][j], sell[j][z]-buy[i][z]);
            }
        }
    }
    printf("%lld", binsearch(0, (LL)inf));
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld", &buy[i][j], &sell[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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