Submission #402752

#	Time	Username	Problem	Language	Result	Execution time	Memory
402752		Hazem	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	74 ms	4164 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 2e5+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 1e14;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

LL s[M][M*10],b[M][M*10];
LL dis[M][M],profit[M][M],dis1[M][M];

int main(){

    //freopen("out.txt","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            scanf("%lld%lld",&b[i][j],&s[i][j]);

    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v] = dis[v][u] = w;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&!dis[i][j])
                dis[i][j] = INF;
                
    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[j][k]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int j1=1;j1<=k;j1++)
                if(b[i][j1]!=-1&&s[j][j1]!=-1)
                    profit[i][j] = max(profit[i][j],s[j][j1]-b[i][j1]);

    LL l = 0,r = 1e9;
    while(l<r){

        int mid = (l+r+1)/2;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis1[i][j] = dis[i][j]*mid-profit[i][j];
        
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    dis1[i][j] = min(dis1[i][j],dis1[i][k]+dis1[k][j]);

        bool q = 0;
        for(int i=1;i<=n;i++)
            q |= dis1[i][i]<0;

        if(q)l = mid;
        else r = mid-1;
    }
    printf("%lld\n",l);
}   

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("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |             scanf("%lld%lld",&b[i][j],&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d%d%d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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