Submission #336043

#	Time	Username	Problem	Language	Result	Execution time	Memory
336043		CaroLinda	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	196 ms	3820 KiB

merchant

#include <bits/stdc++.h>

#define eps 0.000000001
#define debug printf
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

const int MAXN = 110 ;
const int MAXK = 1010 ;
const double inf = 10000000000000.0 ;

using namespace std ;

int N , M , K ;
ll buying[MAXN][MAXK] , selling[MAXN][MAXK] ;
double dist[MAXN][MAXN ] , cost[MAXN][MAXN] ;
double d[MAXN] ;

bool test(double val)
{

	for(int i = 2 ; i <= N ; i++ ) d[i] = inf ;

	for(int i = 1 ; i <= N ; i++ )
		for(int j = 1 ; j <= N ; j++ )
			for(int g = 1 ; g <= N ; g++ )
			{
				if( dist[j][g] > (DBL_MAX/val) ) continue ;
				if( d[j] > d[g] + dist[j][g] * val - cost[j][g] )
					d[j] = d[g] + dist[j][g] * val - cost[j][g] ;
			}

	for(int j = 1 ; j <= N  ;j++ )
		for(int g = 1 ; g <= N ; g++ )
		{
			for(int g = 1 ; g <= N ; g++ )
			{
				if( dist[j][g] > (DBL_MAX/val) ) continue ;
				if( d[j] > d[g] + dist[j][g] * val - cost[j][g] ) return true ;
			}

		}

	return false ;

}

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", &buying[i][j], &selling[i][j] ) ;
	
	for(int i = 1 ; i <= N ; i++ )
		for(int j = i+1 ; j <= N ; j++ ) dist[i][j] = dist[j][i] = inf ;

	for(int i = 1 ,u,v,t ; i <= M ; i++ )
	{
		scanf("%d %d %d", &u, &v, &t ) ;
		dist[u][v] = (double)t ;
	}

	for(int i = 1 ; i <= N ; i++ )
		for(int j= 1 ; j <= N ; j++ )
			for(int g = 1 ; g <= N ; g++ )
				dist[i][j] = min(dist[i][j], dist[i][g] + dist[g][j] ) ;

	for(int i = 1 ; i<= N ; i++ )
		for(int j = 1 ; j <= N ; j++ )
		{
			ll best = 0LL ;

			for(int k = 1 ; k <= K ; k++ )
				if( buying[i][k] != -1 && selling[j][k] != -1 )
					best = max(best, -buying[i][k] + selling[j][k] ) ;

			cost[i][j] = (double)best ;
		}					

	ll l = 0 , r = 1000000000000000LL , mid , best = 0LL ;

	while( l <= r )
	{
		mid = (l+r) >> 1 ;

		if(test((double)mid-eps) )
		{
			best = mid ;
			l = mid+1 ;
		}
		else r = mid-1 ;

	} 


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

}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%d %d %d", &N, &M, &K) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:53:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   for(int j = 1 ; j <= K ; j++ ) scanf("%lld %lld", &buying[i][j], &selling[i][j] ) ;
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d %d %d", &u, &v, &t ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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