# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
57350 | 2018-07-14T15:34:17 Z | gabrielsimoes | Travelling Merchant (APIO17_merchant) | C++17 | 237 ms | 1912 KB |
#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 ll INF = 1e14; // const ll INF = 1000; 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[MAXN]; bool ok[MAXN]; bool testPosCycle(ll x) { // for (int i = 1; i <= N; i++) dist[i] = INF; memset(ok, 0, sizeof(ok)); dist[1] = 0; ok[1] = true; for (int cnt = 0; cnt <= N; cnt++) { for (int i = 1; i <= N; i++) { if (!ok[i]) continue; for (int j = 1; j <= N; j++) { if (i == j) continue; ll dd = dist[i] + gain[i][j] - x*d[i][j]; if (!ok[j] || dd > dist[j]) { dist[j] = dd; ok[j] = true; } if (i != 1 && j == 1 && cnt == N && (dd > dist[i] || dd == 0)) return true; } } } // for (int i = 1; i <= N; i++) { // printf("x %d i %d dist %lld\n", x, i, dist[i]); // } return false; } 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 l = 0, r = INF; while (l < r) { ll m = (l + r + 1LL) >> 1; if (testPosCycle(m)) l = m; else r = m-1; } printf("%lld\n", l); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 237 ms | 1912 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 36 ms | 1912 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 187 ms | 1912 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 36 ms | 1912 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |