제출 #551338

#제출 시각아이디문제언어결과실행 시간메모리
551338nicholask여행하는 상인 (APIO17_merchant)C++14
100 / 100
152 ms4448 KiB
#include <bits/stdc++.h> #define int long long #define x first #define y second #define pb push_back using namespace std; using pii=pair <int,int>; int n,m,k; int buy[101][1001],sell[101][1001]; vector <pii> g[101]; int p[101][101],d[101][101],nw[101][101]; signed main(){ 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]; } for (int i=0; i<m; i++){ int u,v,w; cin>>u>>v>>w; g[u].pb({v,w}); } for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++){ p[i][j]=0; for (int l=1; l<=k; l++){ if (buy[i][l]!=-1&&sell[j][l]!=-1) p[i][j]=max(p[i][j],-buy[i][l]+sell[j][l]); } } } for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++) d[i][j]=1e18; d[i][i]=0; } for (int i=1; i<=n; i++){ for (auto j:g[i]) d[i][j.x]=min(d[i][j.x],j.y); } for (int l=1; l<=n; l++){ for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++) d[i][j]=min(d[i][j],d[i][l]+d[l][j]); } } int l=0,r=2e9; while (l<r){ int mid=(l+r+1)/2; for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++){ if (i==j) nw[i][j]=-1e13; else if (d[i][j]!=1e18) nw[i][j]=p[i][j]-mid*d[i][j]; else nw[i][j]=-1e13; } } for (int l=1; l<=n; l++){ for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++) nw[i][j]=max(nw[i][j],nw[i][l]+nw[l][j]); } } bool found=0; for (int i=1; i<=n; i++){ if (nw[i][i]>=0) found=1; } if (found) l=mid; else r=mid-1; } 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...