| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1191914 | mannshah1211 | Travelling Merchant (APIO17_merchant) | C++17 | 0 ms | 0 KiB |
/**
* author: tourist
* created: 25.04.2025 19:27:44
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
const long long inf = (long long) 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> buy(n, vector<int>(k)), sell(n, vector<int>(k));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
cin >> buy[i][j] >> sell[i][j];
}
}
vector<vector<long long>> profit(n, vector<long long>(n)), dist(n, vector<long long>(n, inf));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int item = 0; item < k; item++) {
if (buy[i][item] != -1 && sell[j][item] != -1) {
profit[i][j] = max(profit[i][j], int64_t(sell[j][item] - buy[i][item]));
}
}
}
}
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
long long t;
cin >> t;
--u; --v;
dist[u][v] = min(dist[u][v], t);
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
auto Check = [&](int mid) {
vector<vector<long long>> d(n, vector<long long>(n, inf));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] != inf) {
d[i][j] = int64_t(mid) * int64_t(dist[i][j]) - profit[i][j];
}
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
if (i == j && d[i][j] <= 0) {
return true;
}
}
}
}
return false;
};
int low = 0, high = 1e9, ans = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (Check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << '\n';
return 0;
}