# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
50122 | mohammad_kilani | Travelling Merchant (APIO17_merchant) | C++17 | 275 ms | 2028 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;
#define mod 1000000007
#define oo 2000000000
const int N = 150 , K = 1100;
long long dist[N][N] , best[N][N];
long double cur[N][N];
int b[N][K] , s[N][K];
int n , m , k , u , v , w;
bool check(long long mid){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i == j) continue;
cur[i][j] = (long double)dist[i][j] * mid - best[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(i == j || i == k) continue;
cur[j][k] = min(cur[j][k],cur[j][i] + cur[i][k]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i != j)
if(cur[i][j] + (long double)mid * dist[j][i] <= 0.00001)
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<=n;j++){
if(i != j)
dist[i][j] = 1e18;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
scanf("%d%d",&b[i][j],&s[i][j]);
}
}
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
dist[u][v] = min(dist[u][v],(long long)w);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
dist[j][k] = min(dist[j][k],(long long) dist[j][i] + dist[i][k]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i == j) continue;
for(int l=1;l<=k;l++){
if(b[i][l] != -1 && s[j][l] != -1)
best[i][j] = max(best[i][j], (long long)s[j][l] - b[i][l]);
}
}
}
long long low = 1 , high = 1e11 , ans = 0 , mid = 0;
while(high >= low){
mid = (low + high) / 2;
if(check(mid)){
ans = mid;
low = mid + 1;
continue;
}
else
high = mid - 1;
}
cout << ans << endl;
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... |