| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 497152 | Sohsoh84 | Travelling Merchant (APIO17_merchant) | C++17 | 0 ms | 0 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 long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 100 + 10;
const ll MAXK = 1000 + 10;
const ll INF = 1e9 + 10; // ?
ll n, m, k, B[MAXN][MAXK], S[MAXN][MAXK], max_prof[MAXN][MAXN], tdist[MAXN][MAXN];
int dist[MAXN][MAXN];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for (int i = 0; i < MAXN; i++) {
memset(dist[i], 63, sizeof dist[i]);
dist[i][i] = 0;
}
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 <= m; i++) {
int u, v, d;
cin >> u >> v >> d;
dist[u][v] = min(dist[u][v], 1ll * d);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int t = 1; t <= k; t++)
if (S[j][t] >= 0 && B[i][t] >= 0)
max_prof[i][j] = max(max_prof[i][j], S[j][t] - B[i][t]);
if (dist[i][j] == INF) max_prof[i][j] = 0;
}
}
ll l = 0, r = ll(2e9) + 10;
while (l < r) {
ll mid = (l + r + 1) >> 1;
bool flag = false;
memset(tdist, 63, sizeof tdist); //
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
tdist[i][j] = min(tdist[i][j], dist[i][j] * mid - max_prof[i][j]); //
// cerr << tdist[i][j] << sep;
}
// cerr << endl;
}
for (int k = 1; k <= n; k++)
for (int v = 1; v <= n; v++)
for (int u = 1; u <= m; u++)
tdist[v][u] = min(tdist[v][u], tdist[v][k] + tdist[k][u]);
// loops
for (int v = 1; v <= n; v++)
for (int u = 1; u <= n; u++)
if (v != u)
flag |= (tdist[v][u] + tdist[u][v] <= 0);
if (flag) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}