제출 #647627

#제출 시각아이디문제언어결과실행 시간메모리
647627ToroTN여행하는 상인 (APIO17_merchant)C++14
100 / 100
103 ms2140 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long ll n,m,num,b[105][1005],s[105][1005],u_i,v_i,w_i,d[105][105],profit[105][105],dis[105][105],type; int main() { scanf("%lld%lld%lld",&n,&m,&num); for(int i=1;i<=n;i++) { for(int j=1;j<=num;j++) { scanf("%lld%lld",&b[i][j],&s[i][j]); } for(int j=1;j<=n;j++)d[i][j]=1e18; } for(int i=1;i<=m;i++) { scanf("%lld%lld%lld",&u_i,&v_i,&w_i); d[u_i][v_i]=w_i; } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=num;k++) { if(b[i][k]!=-1&&s[j][k]!=-1) { profit[i][j]=max(profit[i][j],s[j][k]-b[i][k]); } } } } ll st=1,md,ed=1e9; while(ed>=st) { md=(st+ed)/2; //printf("%lld %lld %lld\n",st,md,ed); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { ////// /*if(d[i][j]>1e18/md) { dis[i][j]=1e18; }else { dis[i][j]=d[i][j]*md-profit[i][j]; }*/ /////// dis[i][j]=md*min(d[i][j],(ll)1e18/md)-profit[i][j]; //printf("%lld ",dis[i][j]); } //printf("\n"); } 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]); } } } type=-1; for(int i=1;i<=n;i++) { if(dis[i][i]<=0) { type=0; } } if(type==0) { st=md+1; }else { ed=md-1; } } //printf("%lld %lld %lld\n",st,md,ed); printf("%lld",ed); }

컴파일 시 표준 에러 (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,&num);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:12:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             scanf("%lld%lld",&b[i][j],&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%lld%lld%lld",&u_i,&v_i,&w_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...