제출 #748173

#제출 시각아이디문제언어결과실행 시간메모리
748173c2zi6여행하는 상인 (APIO17_merchant)C++14
100 / 100
155 ms4272 KiB
#include <bits/stdc++.h> using namespace std; using ld = long double; using ll = long long; ll n; vector<vector<ll>> cst, prf; bool can(ll ans) { vector<vector<ll>> gp(n, vector<ll>(n)); for (ll u = 0; u < n; u++) { for (ll v = 0; v < n; v++) { if (cst[u][v] >= 5e17 / ans) gp[u][v] = -1e18; else gp[u][v] = prf[u][v] - cst[u][v] * ans; } } for (ll k = 0; k < n; k++) { for (ll u = 0; u < n; u++) { for (ll v = 0; v < n; v++) { gp[u][v] = max(gp[u][v], gp[u][k] + gp[k][v]); } } } for (int i = 0; i < n; i++) { if (gp[i][i] >= 0) return true; } return false; } void solve() { ll m, k; cin >> n >> m >> k; vector<vector<ll>> b(n), s(n); for (ll i = 0; i < n; i++) { for (ll j = 0; j < k; j++) { ll x, y; cin >> x >> y; b[i].push_back(x); s[i].push_back(y); } } cst = vector<vector<ll>>(n, vector<ll>(n, 1e18)); for (ll i = 0; i < m; i++) { ll u, v, t; cin >> u >> v >> t; u--, v--; cst[u][v] = t; } for (ll k = 0; k < n; k++) { for (ll u = 0; u < n; u++) { for (ll v = 0; v < n; v++) { cst[u][v] = min(cst[u][v], cst[u][k] + cst[k][v]); } } } prf = vector<vector<ll>>(n, vector<ll>(n, 0)); for (ll u = 0; u < n; u++) { for (ll v = 0; v < n; v++) { for (ll i = 0; i < k; i++) { if (s[v][i] == -1 || b[u][i] == -1) continue; prf[u][v] = max(prf[u][v], s[v][i] - b[u][i]); } } } /* for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { cout << cst[u][v] << " "; } cout << endl; } cout << endl; for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { cout << prf[u][v] << " "; } cout << endl; } cout << endl; */ ll l = 0, r = 1e11; while (l + 1 < r) { ll m = (l + r) / 2; if (can(m)) l = m; else r = m; } cout << l << endl; } int main() { int t = 1; //cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...