# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
347586 | happypotato | 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>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
using namespace std;
const int mxN = 101, mxK = 1001;
vector<pii> adj[mxN];
int a[mxN][mxK][2];
int n, m, k;
void solve();
void subtask1(), subtask2(), subtask3(), subtask4();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve(i);
}
void solve(int case_no) {
// implementation
cin >> n >> m >> k;
bool subtask[3] = {true, true, true};
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= k;j++) {
cin >> a[i][j][0] >> a[i][j][1];
if (i != -1 && a[i][j][0] != -1) subtask[0] = false;
}
}
for (int i = 1;i <= m;i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].eb(v, w);
}
if (subtask[0]) return subtask1();
}
int dfs(int u, int ptr, int dist, int maxi) {
if (u == 1 && dist != 0) {
return maxi / dist;
}
if (dist > 1e9) return 0;
maxi = max(maxi, a[u][ptr][1] - a[1][ptr][0]);
int ans = 0;
for (pii v : adj[u]) {
ans = max(ans, dfs(v.ff, ptr, dist + v.ss, maxi));
}
return ans;
}
void subtask1() {
int ans = 0;
for (int i = 1;i <= k;i++) {
ans = max(ans, dfs(1, i, 0, 0));
}
cout << ans << endl;
}