제출 #655594

#제출 시각아이디문제언어결과실행 시간메모리
655594bebra여행하는 상인 (APIO17_merchant)C++17
100 / 100
107 ms4140 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define dbg(x) cerr << #x << ": " << x << endl; const int INF = 1e9; const int MAX_N = 100; const int MAX_K = 1000; int b[MAX_N][MAX_K]; int s[MAX_N][MAX_K]; int max_earn[MAX_N][MAX_N]; int dist[MAX_N][MAX_N]; int new_dist[MAX_N][MAX_N]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; for (int v = 0; v < n; ++v) { for (int i = 0; i < k; ++i) { cin >> b[v][i] >> s[v][i]; } } for (int i = 0; i < MAX_N; ++i) { for (int j = 0; j < MAX_N; ++j) { dist[i][j] = INF; } } for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u, --v; int w; cin >> w; dist[u][v] = w; } for (int u = 0; u < n; ++u) { for (int v = 0; v < n; ++v) { for (int i = 0; i < k; ++i) { if (s[v][i] == -1 || b[u][i] == -1) continue; max_earn[u][v] = max(max_earn[u][v], s[v][i] - b[u][i]); } } } for (int w = 0; w < n; ++w) { for (int u = 0; u < n; ++u) { for (int v = 0; v < n; ++v) { dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]); } } } auto check = [&](int x) { if (x == 0) return true; for (int u = 0; u < n; ++u) { for (int v = 0; v < n; ++v) { if (dist[u][v] == INF) { new_dist[u][v] = -INF; } else { new_dist[u][v] = max_earn[u][v] - x * dist[u][v]; } } } for (int w = 0; w < n; ++w) { for (int u = 0; u < n; ++u) { for (int v = 0; v < n; ++v) { if (new_dist[u][w] >= INF || new_dist[w][v] >= INF) { new_dist[u][w] = INF; } else { new_dist[u][v] = max(new_dist[u][v], new_dist[u][w] + new_dist[w][v]); } } } } for (int v = 0; v < n; ++v) { if (new_dist[v][v] >= 0) { return true; } } return false; }; int l = 0; int r = 1e9 + 1; while (l != r - 1) { int mid = (l + r) / 2; if (check(mid)) { l = mid; } else { r = mid; } } cout << l << '\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...