# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
163433 | 2019-11-13T10:03:12 Z | KonaeAkira | 여행하는 상인 (APIO17_merchant) | C++17 | 141 ms | 2232 KB |
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int MAX_N = 1e2 + 5; const int MAX_K = 1e3 + 5; int n, m, k, buy[MAX_K], sell[MAX_N], prof[MAX_N][MAX_N], dist[MAX_N][MAX_N]; long long last_prof[MAX_N], last_dist[MAX_N], ans; struct data { int ind; long long prof, dist; }; bool operator < (const data &lhs, const data &rhs) { return lhs.dist > rhs.dist; } void solve(int s) { memset(last_prof, 0xff, sizeof(last_prof)); memset(last_dist, 0x00, sizeof(last_dist)); std::priority_queue<data> q; for (int i = 1; i <= n; ++i) q.push({i, prof[s][i], dist[s][i]}); while (!q.empty()) { data cur = q.top(); q.pop(); //printf("%d %lld %lld\n", cur.ind, cur.prof, cur.dist); if (last_prof[cur.ind] * cur.dist < cur.prof * last_dist[cur.ind]) { last_prof[cur.ind] = cur.prof; last_dist[cur.ind] = cur.dist; ans = std::max(ans, (cur.prof + prof[cur.ind][s]) / (cur.dist + dist[cur.ind][s])); //printf("ans %lld\n", ans); for (int i = 1; i <= n; ++i) if (last_prof[i] * dist[cur.ind][i] < prof[cur.ind][i] * last_dist[i]) q.push({i, cur.prof + prof[cur.ind][i], cur.dist + dist[cur.ind][i]}); } } } int main() { memset(dist, 0x3f, sizeof(dist)); memset(buy, 0x7f, sizeof(buy)); memset(sell, 0x7f, sizeof(sell)); scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) for (int j = 0; j < k; ++j) { int b, s; scanf("%d%d", &b, &s); if (b != -1) { buy[i] = b; sell[i] = s; } } for (int i = 0; i < m; ++i) { int u, v, d; scanf("%d%d%d", &u, &v, &d); dist[u][v] = d; } for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) for (int k = 1; k <= n; ++k) dist[j][k] = std::min(dist[j][k], dist[j][i] + dist[i][k]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) for (int p = 0; p < k; ++p) prof[i][j] = std::max(prof[i][j], sell[j] - buy[i]); for (int i = 1; i <= n; ++i) solve(i); printf("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 125 ms | 2232 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 141 ms | 944 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |