Submission #487997

#TimeUsernameProblemLanguageResultExecution timeMemory
487997MahfelTravelling Merchant (APIO17_merchant)C++17
0 / 100
74 ms2196 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MXN = 120 , MXM = 10000 , MXK = 1020 , Inf = 1e15 + 7; ll n,m,k; ll profit[MXN][MXN] , dis[MXN][MXN]; ll buy[MXN][MXK] , sell[MXN][MXK]; ll gr[MXN][MXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n >> m >> k; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= k ; j++) { cin >> buy[i][j] >> sell[i][j]; if(buy[i][j] == -1) buy[i][j] = Inf; if(sell[i][j] == -1) sell[i][j] = -Inf; } } for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { dis[i][j] = Inf; } dis[i][i] = 0; } for(int i = 0 ; i < m ; i++) { ll v,u,w; cin >> v >> u >> w; dis[v][u] = w; } 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]); } } } for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { for(int x = 1 ; x <= k ; x++) { profit[i][j] = max(profit[i][j] , sell[j][x] - buy[i][x]); } } } // for(int i = 1 ; i <= n ; i++) { // for(int j = 1 ; j <= n ; j++) { // cout << "(" << profit[i][j] << "," << dis[i][j] << ") "; // } // cout << "\n"; // } ll l = 0 , r = 1000000000000; while(r-l > 1) { ll m = (l+r)/2; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { gr[i][j] = dis[i][j]*m - profit[i][j]; if(i == j) gr[i][j] = 0; } } for(int k = 1 ; k <= n ; k++) { for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { gr[i][j] = min(gr[i][j] , gr[i][k] + gr[k][j]); } } } bool ok = 0; for(int i = 1 ; i <= n ; i++) { // cout << i << ": " << gr[i][i] << "\n"; for(int j = i+1 ; j <= n ; j++) { if(gr[i][j] + gr[j][i] <= 0) { ok = 1; break; } } if(ok) break; } if(ok) { l = m; // ans = "YES\n"; } else { r = m; // ans = "NO\n"; } } cout << l << "\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...