# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
295264 | BeanZ | Travelling Merchant (APIO17_merchant) | C++14 | 88 ms | 2156 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 ll long long
#define endl '\n'
const int N = 1e5 + 5;
ll dp[105][105], p[105][105], dist[105][105], b[105][1005], s[105][1005];
bool chk(ll mid, ll n){
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
dp[i][j] = p[i][j] - mid * dist[i][j];
}
}
for (int k = 1; k <= n; k++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (i != j) dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (i != j && (dp[i][j] + dp[j][i]) >= 0) return true;
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("balance.in", "r")){
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
}
ll n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
cin >> b[i][j] >> s[i][j];
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
dist[i][j] = 1e10;
}
}
for (int i = 1; i <= m; i++){
ll u, v, c;
cin >> u >> v >> c;
dist[u][v] = c;
}
for (int x = 1; x <= n; x++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
}
}
for (int x = 1; x <= k; x++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (b[i][k] > 0 && s[j][k] > 0) p[i][j] = max(p[i][j], s[j][k] - b[i][k]);
}
}
}
ll l = 0, h = 1e9;
while (l <= h){
ll mid = (l + h) >> 1;
if (chk(mid, n)) l = mid + 1;
else h = mid - 1;
}
cout << max(h, 0ll);
}
/*
*/
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... |