# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
367988 | parsabahrami | Travelling Merchant (APIO17_merchant) | C++17 | 228 ms | 1388 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.
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 110, M = 9905, K = 1e3 + 10;
int n, m, k, w[M], from[M], to[M], S[N][K], B[N][K]; ll dp[N][N], C[N][N];
void Fill() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = -1e18;
if (i == j) dp[i][j] = 0;
}
}
}
int check(ll x) {
Fill();
for (int i = 1; i <= m; i++) {
int u = from[i], v = to[i];
dp[u][v] = max(dp[u][v], 1ll * -w[i] * x);
}
for (int p = 1; p <= n; p++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) dp[i][j] = min((ll) 1e18, max(dp[i][j], dp[i][p] + dp[p][j]));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) dp[i][j] += C[i][j];
for (int p = 1; p <= n; p++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) dp[i][j] = min((ll) 1e18, max(dp[i][j], dp[i][p] + dp[p][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 1;
return 0;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
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 = 1; i <= m; i++) {
scanf("%d%d%d", &from[i], &to[i], &w[i]);
}
for (int u = 1; u <= n; u++) {
for (int v = 1; v <= n; v++) {
for (int i = 1; i <= k; i++)
if (~B[u][i] && ~S[v][i]) C[u][v] = max(C[u][v], (ll) S[v][i] - B[u][i]);
}
}
ll l = 0, r = 1e15;
while (r - l > 1) {
ll mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid;
}
printf("%lld\n", l);
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... |