제출 #1110679

#제출 시각아이디문제언어결과실행 시간메모리
1110679Icelast여행하는 상인 (APIO17_merchant)C++17
100 / 100
51 ms2316 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 1e9+9; void solve(){ int n, m, k; cin >> n >> m >> k; vector<vector<ll>> buy(n+1, vector<ll>(k+1)), sell(n+1, vector<ll>(k+1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= k; j++){ cin >> buy[i][j] >> sell[i][j]; } } vector<vector<ll>> adj(n+1, vector<ll>(n+1, INF)); for(int i = 1; i <= m; i++){ ll u, v, w; cin >> u >> v >> w; adj[u][v] = w; } vector<vector<ll>> just_profit(n+1, vector<ll>(n+1, 0)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ for(int v = 1; v <= k; v++){ if(buy[i][v] != -1 && sell[j][v] != -1){ just_profit[i][j] = max(just_profit[i][j], sell[j][v]-buy[i][v]); } } } } vector<vector<ll>> shortest_path(n+1, vector<ll>(n+1, INF)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ shortest_path[i][j] = adj[i][j]; } } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ shortest_path[i][j] = min(shortest_path[i][j], shortest_path[i][k]+shortest_path[k][j]); } } } auto check = [&](ll x) -> bool{ vector<vector<ll>> f(n+1, vector<ll>(n+1, -INF)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ f[i][j] = just_profit[i][j] - shortest_path[i][j]*x; } } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ f[i][j] = max(f[i][j], f[i][k]+f[k][j]); } } } for(int i = 1; i <= n; i++){ if(f[i][i] >= 0) return true; } return false; }; ll l = 0, r = 1e9; while(l <= r){ ll mid = (l+r)/2; if(check(mid)){ l = mid+1; }else{ r = mid-1; } } cout << l-1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); 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...