# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
57390 | gabrielsimoes | Travelling Merchant (APIO17_merchant) | C++17 | 42 ms | 1912 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;
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 101, MAXM = 9901, MAXK = 1001;
const ll INF = 1e16;
// const ll INF = 1000;
int N, M, K;
ll buy[MAXN][MAXK];
ll sell[MAXN][MAXK];
ll maxAns = 0;
bool reaches[MAXN][MAXN];
ll d[MAXN][MAXN];
ll gain[MAXN][MAXN];
ll dist[MAXN][MAXN];
bool ok[MAXN];
bool testPosCycle(ll x) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
dist[i][j] = gain[i][j] - x * d[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 && reaches[i][k] && reaches[k][j]) {
dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j && reaches[i][j] && reaches[j][i] && dist[i][j] + dist[j][i] >= 0) {
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d%d", &N, &M, &K);
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= K; k++) {
scanf("%lld%lld", &buy[i][k], &sell[i][k]);
}
}
for (int i = 1,a,b,c; i <= M; i++) {
scanf("%d%d%d", &a, &b, &c);
d[a][b] = c;
reaches[a][b] = true;
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j && reaches[i][k] && reaches[k][j]) {
if (!reaches[i][j]) {
reaches[i][j] = true;
d[i][j] = d[i][k] + d[k][j];
} else {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j && reaches[i][j] && reaches[j][i]) {
maxAns = max(maxAns, d[i][j] + d[j][i]);
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= K; k++) {
if (buy[i][k] != -1 && sell[j][k] != -1) {
gain[i][j] = max(gain[i][j], -buy[i][k] + sell[j][k]);
}
}
}
}
ll ans = 0;
for (int i = 2; i <= N; i++) {
if (reaches[1][i] && reaches[i][1])
ans = max(ans, gain[1][i]/(d[1][i] + d[i][1]));
}
printf("%lld\n", ans);
// ll l = 0, r = maxAns;
// while (l < r) {
// ll m = (l + r + 1LL) >> 1;
// if (testPosCycle(m)) l = m;
// else r = m-1;
// }
// printf("%lld\n", l);
}
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... |