# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
567732 | shahriarkhan | Travelling Merchant (APIO17_merchant) | C++14 | 95 ms | 4284 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std ;
const int MX_N = 105 , MX_K = 1005 ;
const long long INF = 1e18 + 5 ;
int n , m , k ;
long long dist[MX_N][MX_N] , best[MX_N][MX_N] , buy[MX_N][MX_K] , sell[MX_N][MX_K] , profit[MX_N][MX_N] ;
void floyd_warshall(long long dst[MX_N][MX_N])
{
for(int l = 1 ; l <= n ; ++l)
{
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
{
dst[i][j] = min(dst[i][j],dst[i][l]+dst[l][j]) ;
}
}
}
}
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)
{
dist[i][j] = INF ;
}
}
for(int i = 1 ; i <= m ; ++i)
{
long long v , w , t ;
scanf("%lld%lld%lld",&v,&w,&t) ;
dist[v][w] = t ;
}
floyd_warshall(dist) ;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
{
for(int l = 1 ; l <= k ; ++l)
{
if(buy[i][l]<0) continue ;
if(sell[j][l]<0) continue ;
best[i][j] = max(best[i][j],sell[j][l]-buy[i][l]) ;
}
}
}
long long low = 0 , high = 1e9 + 5 ;
while(low<high)
{
long long mid = (low+high+1)/2 , good = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
{
profit[i][j] = mid*min(INF/mid,dist[i][j]) - best[i][j] ;
}
}
floyd_warshall(profit) ;
for(int i = 1 ; i <= n ; ++i)
{
if(profit[i][i]<=0) good = 1 ;
}
if(good) low = mid ;
else high = mid - 1 ;
}
printf("%lld\n",low) ;
return 0 ;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |