제출 #111456

#제출 시각아이디문제언어결과실행 시간메모리
111456diamond_duke여행하는 상인 (APIO17_merchant)C++11
0 / 100
74 ms1280 KiB
#include <algorithm> #include <cstring> #include <cstdio> using ll = long long; inline void floyd(ll dis[][105], int n) { for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]); } } } int buy[105][1005], sell[105][1005], profit[105][105]; ll dis[105][105], cost[105][105]; int main() { // freopen("APIO2017-T3.in", "r", stdin); int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) scanf("%d", buy[i] + j); for (int j = 0; j < k; j++) scanf("%d", sell[i] + j); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int x = 0; x < k; x++) { if (~buy[i][x] && ~sell[j][x]) profit[i][j] = std::max(profit[i][j], sell[j][x] - buy[i][x]); } } } memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dis[--u][--v] = w; } floyd(dis, n); int l = 0, r = 1e9, res = -1; while (l <= r) { int mid = l + r >> 1; memset(cost, 0x3f, sizeof(cost)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dis[i][j] < 1e18) cost[i][j] = (ll)dis[i][j] * mid - profit[i][j]; } } floyd(cost, n); bool flg = false; for (int i = 0; i < n; i++) flg |= cost[i][i] <= 0; if (flg) { res = mid; l = mid + 1; } else r = mid - 1; } printf("%d\n", res); return 0; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
merchant.cpp:22: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:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", buy[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~
merchant.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", sell[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &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...