제출 #566691

#제출 시각아이디문제언어결과실행 시간메모리
566691ngpin04여행하는 상인 (APIO17_merchant)C++14
100 / 100
171 ms3348 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 105; const int K = 1005; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); long long cost[N][N]; long long dis[N][N]; int prof[N][N]; int d[N][N]; int b[N][K]; int s[N][K]; int cnt[N]; int n,m,k; bool inq[N]; bool solve(int x) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = -ooo; for (int i = 1; i <= n; i++) for (int k = 1; k <= n; k++) for (int j = 1; j <= n; j++) if (d[i][j] < oo && d[j][k] < oo) { if (i == j && j == k) continue; // cerr << i << " " << j << " " << k << "\n"; // cerr << prof[j][k] << "\n"; // cerr << d[i][j] << " " << d[j][k] << "\n"; maxi(dis[i][k], prof[j][k] - 1LL * (d[i][j] + d[j][k]) * x); } // for (int i = 1; i <= n; i++) // for (int j = 1; j <= n; j++) // cerr << i << " " << j << " " << cost[i][j] << "\n"; for (int j = 1; j <= n; j++) for (int i = 1; i <= n; i++) for (int k = 1; k <= n; k++) maxi(dis[i][k], dis[i][j] + dis[j][k]); for (int i = 1; i <= n; i++) if (dis[i][i] >= 0) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef ONLINE_JUDGE // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); #endif cin >> n >> m >> k; for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) cin >> b[i][j] >> s[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) d[i][j] = oo; for (int i = 1; i <= m; i++) { int u,v,w; cin >> u >> v >> w; mini(d[u][v], w); } for (int j = 1; j <= n; j++) for (int i = 1; i <= n; i++) for (int k = 1; k <= n; k++) mini(d[i][k], d[i][j] + d[j][k]); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int it = 1; it <= k; it++) if (s[j][it] != -1 && b[i][it] != -1) maxi(prof[i][j], s[j][it] - b[i][it]); int lo = 0; int hi = oo + 1; while (hi - lo > 1) { int mid = (lo + hi) >> 1; if (solve(mid)) lo = mid; else hi = mid; } cout << lo; 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...