| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 551456 | Ai7081 | 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;
#define long long long
#define st first
#define nd second
const int N = 105;
const int K = 1005;
struct data{
long x, t;
data() {}
data(long x, long t) : x(x), t(t) {}
bool operator < (const data &o) const {
if (!t) return true;
if (!o.t) return false;
if (x == 0 && o.x == 0) return t < o.t;
return x*o.t < t*o.x;
}
bool operator > (const data &o) const {return !(*this < o);}
data operator + (const data &o) {return data(x+o.x, t+o.t);}
void operator += (const data &o) {x+=o.x; t+=o.t;}
};
struct node{
data val;
long v;
bool operator < (const node &o) const {return val > o.val;}
};
long n, m, k, b[N][K], s[N][K];
data dis[N][N], out;
vector<pair<long, long>> adj[N];
priority_queue<node> pq;
bool mark[N];
void dfs(long root, long v, long t) {
dis[root][v] = {0, t};
mark[v] = true;
for (int i=1; i<=k; i++) {
if (root == v) break;
if (b[root][i]!=-1 && s[v][i]!=-1) dis[root][v] = max(dis[root][v], {s[v][i]-b[root][i], t});
}
for (auto [to, cost] : adj[v]) if (!mark[to]) dfs(root, to, t+cost);
}
int main() {
scanf(" %lld %lld %lld", &n, &m, &k);
for (int i=1; i<=n; i++) {
for (int j=1; j<=k; j++) scanf(" %lld", &b[i][j]);
for (int j=1; j<=k; j++) scanf(" %lld", &s[i][j]);
}
while (m--) {
long x, y, z;
scanf(" %lld %lld %lld", &x, &y, &z);
adj[x].push_back({y, z});
}
for (int i=1; i<=n; i++) fill_n(mark, N, false), dfs(i, i, 0);
// for (int i=1; i<=n; i++) {
// printf("dis %d : ", i);
// for (int j=1; j<=n; j++) printf("(%lld %lld) ", dis[i][j].x, dis[i][j].t);
// printf("\n");
// }
for (int s=1; s<=n; s++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) if (dis[i][s].t && dis[s][j].t) {
dis[i][j] = max(dis[i][j], dis[i][s] + dis[s][j]);
}
}
}
for (int i=1; i<=n; i++) out = max(out, dis[i][i]);
printf("%lld %lld\n", out.x, out.t);
printf("%lld", out.t ? out.x/out.t : 0);
return 0;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/