제출 #945534

#제출 시각아이디문제언어결과실행 시간메모리
945534NeroZein여행하는 상인 (APIO17_merchant)C++17
100 / 100
96 ms1624 KiB
#include "bits/stdc++.h" using namespace std; #ifdef Nero #include "Deb.h" #else #define debug(...) #endif const int N = 102; const int K = 1003; int n, m, k; int adj[N][N]; int best[N][N]; long long p[N][N]; long long adj2[N][N]; int buy[N][K], sell[N][K]; void pre() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { for (int l = 1; l <= k; ++l) { if (sell[j][l] != -1 && buy[i][l] != -1) { best[i][j] = max(best[i][j], sell[j][l] - buy[i][l]); } } } } } void floyd() { for (int l = 1; l <= n; ++l) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { adj2[i][j] = min(adj2[i][j], adj2[i][l] + adj2[l][j]); } } } } void floyd2() { for (int l = 1; l <= n; ++l) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { p[i][j] = max(p[i][j], p[i][l] + p[l][j]); } } } } bool check(int mid) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { adj2[i][j] = (long long) adj[i][j] * mid; } } floyd(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { p[i][j] = -adj2[i][j] + best[i][j]; } } floyd2(); for (int i = 1; i <= n; ++i) { if (p[i][i] >= 0) { return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> k; for (int i = 1; i <= n; ++i) { for (int j = 2; j <= 2 * k; j += 2) { cin >> buy[i][j / 2] >> sell[i][j / 2]; } } memset(adj, 0x3f3f3f3f, sizeof adj); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; adj[u][v] = min(adj[u][v], w); } pre(); int lo = 0, hi = 1e9 + 9; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (check(mid)) { lo = mid; } else { hi = mid - 1; } } cout << lo << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...