제출 #278678

#제출 시각아이디문제언어결과실행 시간메모리
278678toonewbie여행하는 상인 (APIO17_merchant)C++17
33 / 100
1094 ms2808 KiB
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define INF 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; int n, m, K; ll d[200][200], a[200][200]; int b[200][2000], s[200][2000]; bool C(ll t) { rep(i, n) rep(j, n) a[i][j] = -INF; rep(i, n) rep(j, n) { if (i == j || d[i][j] == INF) continue; a[i][j] = -t * d[i][j]; rep(k, K) { if (b[i][k] == -1 || s[j][k] == -1) continue; a[i][j] = max(a[i][j], s[j][k] - b[i][k] - t * d[i][j]); } } rep(k, n) rep(i, n) rep(j, n) { a[i][j] = max(a[i][j], a[i][k] + a[k][j]); } rep(i, n) { if (a[i][i] >= 0) return true; } return false; } int main() { cin >> n >> m >> K; rep(i, n) rep(j, K) scanf("%d%d", &b[i][j], &s[i][j]); memset(d, 0x3f, sizeof(d)); rep(i, n) d[i][i] = 0; rep(i, m) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--; b--; d[a][b] = c; } rep(k, n) rep(i, n) rep(j, n) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } ll l = 0, r = INT_MAX; while (r - l > 1) { ll t = (l + r) / 2; if (C(t)) l = t; else r = t; } cout << l << endl; return 0; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:32:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   rep(i, n) rep(j, K) scanf("%d%d", &b[i][j], &s[i][j]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     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...