#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
// const int MAXN = 101, MAXM = 9901, MAXK = 1001;
const int MAXN = 51, MAXK = 51;
const ll INF = 1e18;
int N, M, K;
vector<pii> g[MAXN];
ll buy[MAXN][MAXK];
ll sell[MAXN][MAXK];
ll d[MAXN][MAXN];
ll gain[MAXN][MAXN];
// ll dist[2][MAXN];
// priority_queue<pair<int, ll>, vector<pair<int, ll>>, greater<pair<int, ll>>> q;
// void dijkstra(int start, ll d[], vector<pii> g[]) {
// for (int i = 1; i <= N; i++) d[i] = INF;
// q.push({0, start});
// d[start] = 0;
// while (!q.empty()) {
// ll dd; int cur;
// tie(dd, cur) = q.top();
// q.pop();
// if (dd > d[cur]) continue;
// for (pii p : g[cur]) {
// int nx = p.first;
// ll cost = p.second;
// if (dd + cost < d[nx]) {
// d[nx] = dd + cost;
// q.push({d[nx], nx});
// }
// }
// }
// }
// ll dp[MAXN][MAXN*MAXN][MAXK];
// bool ok[MAXN][MAXN*MAXN][MAXK];
// ll f(int cur, int sum, int bag) {
// if (cur == 1 && sum == 0 && bag == 0) return 0;
// else if (sum <= 0) return -INF;
// ll &ret = dp[cur][sum][bag];
// if (ok[cur][sum][bag]) return ret;
// ok[cur][sum][bag] = true;
// ret = -INF;
// if (bag && sell[cur][bag] != -1) {
// ret = max(ret, f(cur, sum, 0) + sell[cur][bag]);
// }
// if (bag == 0) {
// for (int k = 1; k <= K; k++) {
// if (buy[cur][k] != -1) {
// ret = max(ret, f(cur, sum, k) - buy[cur][k]);
// }
// }
// }
// for (pii p : g[cur]) {
// int nx = p.first;
// int cost = p.second;
// ret = max(ret, f(nx, sum - cost, bag));
// }
// return ret;
// }
int main() {
scanf("%d%d%d", &N, &M, &K);
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= K; k++) {
scanf("%lld%lld", &buy[i][k], &sell[i][k]);
}
}
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= N; k++) {
d[i][k] = INF;
}
d[i][i] = 0;
}
for (int i = 1,a,b,c; i <= M; i++) {
scanf("%d%d%d", &a, &b, &c);
g[a].push_back({b, c});
d[a][b] = c;
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= K; k++) {
if (buy[i][k] != -1 && sell[j][k] != -1) {
gain[i][j] = max(gain[i][j], -buy[i][k] + sell[j][k]);
}
}
}
}
// ll ans = 0;
// for (int sum = 1; sum <= N*N; sum++) {
// ans = max(ans, f(1, sum, 0)/ll(sum));
// }
// for (int sum = 0; sum <= N*N; sum++) {
// printf("dp %d %d %d: %lld\n", 1, sum, 0, f(1, sum, 0));
// }
ll ans = 0;
for (int i = 1; i <= N; i++) {
ll dist = d[1][i] + d[i][1];
if (dist > 0) {
ans = max(ans, gain[1][i]/dist);
}
}
printf("%lld\n", ans);
}
Compilation message
merchant.cpp: In function 'int main()':
merchant.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &M, &K);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &buy[i][k], &sell[i][k]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4 ms |
724 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
