제출 #213519

#제출 시각아이디문제언어결과실행 시간메모리
213519tri여행하는 상인 (APIO17_merchant)C++14
0 / 100
211 ms3576 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; #define pb push_back #define f first #define s second const int MAXN = 105; const int MAXK = 1005; const ll INF = 1e10; ll aM[MAXN][MAXN]; ll trans[2][MAXN][MAXK]; // 0 is buy 1 is sell ll prof[MAXN][MAXN]; ld agg[MAXN][MAXN]; ld best[MAXN]; int N, M, K; bool pos(ld ef) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { agg[i][j] = prof[i][j] - aM[i][j] * ef; } } fill(best, best + MAXN, 0); for (int i = 0; i < N; i++) { for (int cV = 0; cV < N; cV++) { for (int aV = 0; aV < N; aV++) { if (best[aV] < best[cV] + agg[cV][aV]) { best[aV] = best[cV] + agg[cV][aV]; } } } } for (int cV = 0; cV < N; cV++) { for (int aV = 0; aV < N; aV++) { if (best[aV] < best[cV] + agg[cV][aV]) { return true; } } } return false; } ll binSearch() { ll low = 0; ll hi = INF; while (low != hi) { ll mid = (low + hi + 1) / 2; if (pos(mid)) { low = mid; } else { hi = mid - 1; } } if (pos(low + 1 - 1e9)) { return low + 1; } return low; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M >> K; for (int i = 0; i < N; i++) { for (int j = 0; j < K; j++) { cin >> trans[0][i][j] >> trans[1][i][j]; if (trans[0][i][j] == -1) { trans[0][i][j] = INF; } if (trans[1][i][j] == -1) { trans[1][i][j] = -INF; } } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { aM[i][j] = INF; } } for (int i = 0; i < M; i++) { int u, v; ll c; cin >> u >> v >> c; u--, v--; aM[u][v] = c; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { if (aM[j][i] + aM[i][k] < aM[j][k]) { aM[j][k] = aM[j][i] + aM[i][k]; } } } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ll cM = 0; for (int k = 0; k < K; k++) { cM = max(cM, trans[1][j][k] - trans[0][i][k]); } prof[i][j] = cM; } } // cout << pos(2) << endl; ll ans = binSearch(); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...