제출 #549874

#제출 시각아이디문제언어결과실행 시간메모리
549874FEDIKUS여행하는 상인 (APIO17_merchant)C++17
100 / 100
145 ms2568 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=110; const ll maxk=1010; const ll inf=LLONG_MAX/2; ll n,m,k; ll b[maxn][maxk]; ll s[maxn][maxk]; ll gt[maxn][maxn]; ll gp[maxn][maxn]; ll checkg[maxn][maxn]; void init(){ for(int i=0;i<n;i++) for(int j=0;j<n;j++) gt[i][j]=inf; } void floyd(ll g[maxn][maxn]){ for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ for(ll l=0;l<n;l++){ g[j][l]=min(g[j][l],g[j][i]+g[i][l]); } } } } bool check(ll eff){ for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ checkg[i][j]=inf; if(gt[i][j]==inf) continue; checkg[i][j]=eff*gt[i][j]-gp[i][j]; } } floyd(checkg); for(ll i=0;i<n;i++){ if(checkg[i][i]<=0) return true; } return false; } int main(){ cin>>n>>m>>k; init(); for(ll i=0;i<n;i++){ for(ll j=0;j<k;j++) cin>>b[i][j]>>s[i][j]; } for(ll i=0;i<m;i++){ ll v,w,t; cin>>v>>w>>t; v--,w--; gt[v][w]=min(t,gt[v][w]); } floyd(gt); for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ for(ll l=0;l<k;l++){ if(s[j][l]==-1 || b[i][l]==-1) continue; gp[i][j]=max(gp[i][j],s[j][l]-b[i][l]); } } } ll l=0,r=1e9+10,res=-1; while(l<=r){ ll mid=(l+r)/2; if(check(mid)){ res=mid; l=mid+1; }else r=mid-1; } cout<<res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...