Submission #336043

#TimeUsernameProblemLanguageResultExecution timeMemory
336043CaroLindaTravelling Merchant (APIO17_merchant)C++14
0 / 100
196 ms3820 KiB
#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 ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...