제출 #102002

#제출 시각아이디문제언어결과실행 시간메모리
102002bakpark여행하는 상인 (APIO17_merchant)C++14
33 / 100
134 ms1400 KiB
#include <cstdio> #include <algorithm> #include <limits.h> #include <memory.h> using namespace std; #define ll long long int N,M,K; int B[101][1001], S[101][1001], T[101][101]; double val[101][101]; int Q[101][101]; ll dist[101][101]; double g(int st,int en,int m,ll d){ return Q[st][en]-(double)d*m; } bool f(int m){ for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ if(T[i][j]) { dist[i][j] = T[i][j]; val[i][j] = g(i,j,m,dist[i][j]); } else { dist[i][j] = -1ll; val[i][j] = LLONG_MIN; } } } for(int mid=1;mid<=N;mid++){ for(int st=1;st<=N;st++){ for(int en=1;en<=N;en++){ if(dist[st][mid]==-1ll||dist[mid][en]==-1ll) continue; ll td = dist[st][mid]+dist[mid][en]; double hval = max(g(st,en,m,td),val[st][mid]+val[mid][en]); if(hval>val[st][en]){ dist[st][en] = td; val[st][en] = hval; } } } for(int n=1;n<=N;n++){ if(val[n][n]>=0) return true; } } return false; } int main(){ scanf("%d %d %d",&N,&M,&K); for(int i=1;i<=N;i++){ for(int j=0;j<K+K;j++){ int tmp;scanf("%d",&tmp); if(j&1) S[i][j/2+1] = tmp; else B[i][j/2+1] = tmp; } } for(int i=0;i<M;i++){ int a,b,c; scanf("%d %d %d",&a,&b,&c); T[a][b] = c; } for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ for(int k=1;k<=K;k++){ if(i==j) continue; if(B[i][k]>0&&S[j][k]>0) Q[i][j] = max(Q[i][j],S[j][k]-B[i][k]); } } } int l = 0,r = 1000000000,answ=0; while(l<=r){ int m = (l+r)>>1; if(f(m)){ l = m+1; answ = m; } else r = m-1; } printf("%d",answ); }

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

merchant.cpp: In function 'int main()':
merchant.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
merchant.cpp:51:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int tmp;scanf("%d",&tmp);
            ~~~~~^~~~~~~~~~~
merchant.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...