제출 #936331

#제출 시각아이디문제언어결과실행 시간메모리
936331LOLOLO여행하는 상인 (APIO17_merchant)C++17
100 / 100
72 ms4204 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 100 + 10; ll dis[N][N], profit[N][N]; ll b[N][1000 + 10], s[N][1000 + 10], n; ll bin(ll m) { vector < vector <ll>> dd(n + 1, vector <ll> (n + 1, -1e17)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dd[i][j] = profit[i][j] - dis[i][j] * m; } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dd[i][j] = max(dd[i][j], dd[i][k] + dd[k][j]); } } } for (int i = 1; i <= n; i++) { if (dd[i][i] >= 0) { return 1; } } return 0; } ll solve() { int m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { fill(dis[i], dis[i] + n + 1, 1e9); } 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 <= m; i++) { ll a, b, c; cin >> a >> b >> c; dis[a][b] = min(dis[a][b], c); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int f = 1; f <= k; f++) { if (s[j][f] == -1 || b[i][f] == -1) continue; profit[i][j] = max(profit[i][j], s[j][f] - b[i][f]); } } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } ll l = 0, r = 1e9 + 100, ans = 0; while (l <= r) { ll m = (l + r) / 2; if (bin(m)) { ans = m; l = m + 1; } else { r = m - 1; } } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { //solve(); cout << solve() << '\n'; } } /* 4 5 2 10 9 5 2 6 4 20 15 9 7 10 9 -1 -1 16 11 1 2 3 2 3 3 1 4 1 4 3 1 3 1 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...