제출 #406986

#제출 시각아이디문제언어결과실행 시간메모리
406986Waratpp123여행하는 상인 (APIO17_merchant)C++14
0 / 100
123 ms2124 KiB
#include<bits/stdc++.h> using namespace std; long long buy[105][1005],sell[105][1005],dis[105][105],prof[105][105],eff[105][105]; int main(){ long long i,j,n,m,k,p,u,v,w,l,r,mid; scanf("%lld %lld %lld",&n,&m,&p); for(i=1;i<=n;i++){ for(j=1;j<=p;j++){ scanf("%lld %lld",&buy[i][j],&sell[i][j]); } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ dis[i][j]=2e18; prof[i][j]=0; } } for(i=1;i<=m;i++){ scanf("%lld %lld %lld",&u,&v,&w); dis[u][v]=w; } for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(dis[i][k]+dis[k][j]<dis[i][j]){ dis[i][j]=dis[i][k]+dis[k][j]; } } } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(dis[i][j]>1e18){ prof[i][j]=-1e18; continue; } int ch=0; for(k=1;k<=p;k++){ if(sell[j][k]!=-1&&buy[i][k]!=-1) ch=1,prof[i][j]=max(prof[i][j],sell[j][k]-buy[i][k]); } if(ch==0) prof[i][j]=-1e18; } } l=0,r=1e9; while(l<r){ mid=(l+r+1)/2; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(prof[i][j]==-1) eff[i][j]=-1e18; else eff[i][j]=prof[i][j]-mid*dis[i][j]; } } for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(prof[i][j]==-1e18) continue; eff[i][j]=max(eff[i][j],eff[i][k]+eff[k][j]); } } } int ch=0; for(i=1;i<=n;i++) if(eff[i][i]>=0) ch=1; if(ch==1) l=mid; else r=mid-1; } printf("%lld\n",l); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'int main()':
merchant.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%lld %lld %lld",&n,&m,&p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:10:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |             scanf("%lld %lld",&buy[i][j],&sell[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%lld %lld %lld",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...