제출 #551466

#제출 시각아이디문제언어결과실행 시간메모리
551466Ai7081여행하는 상인 (APIO17_merchant)C++17
100 / 100
91 ms2120 KiB
#include <bits/stdc++.h> using namespace std; #define long long long const int N = 105; const int I = 1005; const long inf = 1e18; long n, m, item, x, y, z, dis[N][N], fin[N][N], val[N][N], b[N][I], s[N][I]; int main() { scanf(" %lld %lld %lld", &n, &m, &item); for (int i=1; i<=n; i++) for (int j=1; j<=item; j++) scanf(" %lld %lld", &b[i][j], &s[i][j]); fill_n(dis[0], N*N, inf); while (m--) { scanf(" %lld %lld %lld", &x, &y, &z); dis[x][y] = z; } 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]); } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=item; k++) { if (b[i][k]!=-1 && s[j][k]!=-1) val[i][j] = max(val[i][j], s[j][k] - b[i][k]); } // for (int i=1; i<=n; i++) {for (int j=1; j<=n; j++) printf("%lld " , dis[i][j]); printf("\n");} // for (int i=1; i<=n; i++) {for (int j=1; j<=n; j++) printf("%lld " , val[i][j]); printf("\n");} long l=1, r=1e9; while (l <= r) { long mid = (l+r)>>1; // printf("%lld %lld %lld\n", l, mid, r); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) fin[i][j] = mid * min(dis[i][j], inf/mid) - val[i][j]; for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { fin[i][j] = min(fin[i][j], fin[i][k] + fin[k][j]); } bool ok = false; for (int i=1; i<=n; i++) if (fin[i][i] <= 0) {ok=true; break;} if (ok) l = mid+1; else r = mid-1; } printf("%lld", r); return 0; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf(" %lld %lld %lld", &n, &m, &item);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:13:63: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for (int i=1; i<=n; i++) for (int j=1; j<=item; j++) scanf(" %lld %lld", &b[i][j], &s[i][j]);
      |                                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf(" %lld %lld %lld", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...