Submission #233807

#	Time	Username	Problem	Language	Result	Execution time	Memory
233807		DodgeBallMan	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	127 ms	4600 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
long long d[N][N], g[N][N], cost[N][N], b[N][N*10], s[N][N*10];
int n, m, k;

int check( long long p ) {
    //printf("P : %lld :",p);
    for( int i = 1 ; i <= n ; i++ ) for( int j = 1 ; j <= n ; j++ ) {
        g[i][j] = d[i][j] * p - cost[i][j];
        //printf("%lld",g[i][j]);
    }
    for( int t = 1 ; t <= n ; t++ ) for( int i = 1 ; i <= n ; i++ ) for( int j = 1 ; j <= n ; j++ ) if( i != j ) {
        g[i][j] = min( g[i][j], g[i][t] + g[t][j] );
    }
    for( int i = 1 ; i <= n ; i++ ) for( int j = 1 ; j <= n ; j++ ) if( i != j && g[i][j] + g[j][i] <= 0 ) return 1;
    return 0;
}

int main()
{
    for( int i = 1 ; i < N ; i++ ) for( int j = 1 ; j < N ; j++ ) d[i][j] = 1e9;
    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, u, v ; i <= m ; i++ ) {
        long long di;
        scanf("%d %d %lld",&u,&v,&di);
        d[u][v] = min( d[u][v], di );
    } 
    for( int i = 1 ; i <= n ; i++ ) d[i][i] = 0LL;
    for( int i = 1 ; i <= n ; i++ ) for( int j = 1 ; j <= n ; j++ ) 
        for( int l = 1 ; l <= k ; l++ ) if( b[i][l] != -1LL && s[j][l] != -1LL ) {
            cost[i][j] = max( cost[i][j], s[j][l] - b[i][l] );
        }
    for( int t = 1 ; t <= n ; t++ ) for( int i = 1 ; i <= n ; i++ ) for( int j = 1 ; j <= n ; j++ ) {
        d[i][j] = min( d[i][j], d[i][t] + d[t][j] );
    }
    /*for( int i = 1 ; i <= n ; i++ ) {
        for( int j = 1 ; j <= n ; j++ ) printf("%lld %lld\n",d[i][j],cost[i][j]);
        printf("\n");
    }*/
    long long l = 0, r = 1e9;
    while( r - l > 1 ) {
        long long mid = ( l + r ) / 2;
        // printf("%lld\n",mid);
        if( check( mid ) ) l = mid;
        else r = mid;
    }
    printf("%lld",l);
    return 0;
}

Compilation message (stderr)

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

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