제출 #367417

#제출 시각아이디문제언어결과실행 시간메모리
367417ogibogi2004여행하는 상인 (APIO17_merchant)C++14
100 / 100
168 ms4460 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll INF=2e17; const int MAXN=128; const int MAXK=1024; ll mindist[MAXN][MAXN]; ll maxearn[MAXN][MAXN]; ll n,m,k; ll b[MAXN][MAXK]; ll s[MAXN][MAXK]; ll g[MAXN][MAXN]; bool ok(ll r) { for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { g[i][j]=INF; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(mindist[i][j]>=INF)continue; g[i][j]=r*mindist[i][j]-maxearn[i][j]; } } /*cout<<r<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<g[i][j]<<" "; } cout<<endl; }*/ for(int j=1;j<=n;j++) { for(int i=1;i<=n;i++) { for(int l=1;l<=n;l++) { g[i][l]=min(g[i][l],g[i][j]+g[j][l]); } } } /*cout<<"-------------\n"; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<g[i][j]<<" "; } cout<<endl; }*/ for(int i=1;i<=n;i++) { if(g[i][i]<=0)return 1; } return 0; } int main() { for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { mindist[i][j]=INF; } } cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { cin>>b[i][j]>>s[i][j]; } } for(int i=1;i<=m;i++) { ll v,w,t; cin>>v>>w>>t; mindist[v][w]=min(mindist[v][w],t); } for(int j=1;j<=n;j++) { for(int i=1;i<=n;i++) { for(int l=1;l<=n;l++) { if(mindist[i][j]+mindist[j][l]<mindist[i][l]) { mindist[i][l]=mindist[i][j]+mindist[j][l]; } } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(mindist[i][j]==INF)continue; for(int l=1;l<=k;l++) { if(s[j][l]==-1||b[i][l]==-1)continue; maxearn[i][j]=max(maxearn[i][j],s[j][l]-b[i][l]); } } } ll low=0,high=1000000000,mid,ans; while(low<=high) { mid=(low+high)/2; if(ok(mid)) { ans=mid; low=mid+1; } else high=mid-1; } cout<<ans<<endl; 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...