제출 #885214

#제출 시각아이디문제언어결과실행 시간메모리
885214Hakiers여행하는 상인 (APIO17_merchant)C++17
100 / 100
67 ms4328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; constexpr int MAXN = 1e2 + 7; constexpr ll oo = 8e18; ll dist[MAXN][MAXN]; ll profit[MAXN][MAXN]; ll cycle[MAXN][MAXN]; pair<ll, ll> market[MAXN][1007]; int n, m, k; void computeDist(){ for(int l = 1; l <= n; l++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist[i][l] != oo && dist[l][j] != oo) dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]); } void computeProfit(){ for(int l = 1; l <= k; l++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(market[i][l].first != -1 && market[j][l].second != -1 && dist[i][j] != oo && i != j) profit[i][j] = max(profit[i][j], market[j][l].second - market[i][l].first); } void prepare(ll x){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(dist[i][j] != oo) cycle[i][j] = (dist[i][j] * x) - profit[i][j]; else cycle[i][j] = oo; } } } bool check(ll x){ prepare(x); for(int l = 1; l <= n; l++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist[i][l] != oo && dist[l][j] != oo) cycle[i][j] = min(cycle[i][j], cycle[i][l] + cycle[l][j]); /* for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cout << "i: " << i << " j " << j << " cycle: " << cycle[i][j] << "\n"; for(int l = 1; l <= n; l++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist[i][l] != oo && dist[l][j] != oo) if(cycle[i][j] > cycle[i][l] + cycle[l][j]) return true; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist[i][j] != oo && dist[j][i] != oo && i != j) if(cycle[i][j] + cycle[j][i] <= 0) return true; */ for(int i = 1; i <= n; i++) if(cycle[i][i] <= 0) return true; return false; } ll BS(){ ll l = 0, r = 1e9, mid; while(l < r){ mid = (l+r)/2; if(check(mid)) l = mid + 1; else r = mid; } if(check(l)) return l; return max(--l, (ll)0); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) cin >> market[i][j].first >> market[i][j].second; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dist[i][j] = oo; for(int i = 1; i <= m; i++){ int u, v; ll t; cin >> u >> v >> t; dist[u][v] = min(dist[u][v], t); } computeDist(); computeProfit(); /* for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cout << "i " << i << " j " << j << " profit " << profit[i][j] << "\n"; check(1); cout << "\n"; check(2); cout << "\n"; check(3); cout << "\n"; check(4); cout << "\n"; */ cout << BS() << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...