제출 #554663

#제출 시각아이디문제언어결과실행 시간메모리
554663Tien_Noob여행하는 상인 (APIO17_merchant)C++17
100 / 100
87 ms3308 KiB
//Make CSP great again //Vengeance #include <bits/stdc++.h> #define TASK "TESTCODE" #define Log2(x) 31 - __builtin_clz(x) using namespace std; const int N = 1e2, K = 1e3, oo = 2e9; int d[N + 1][N + 1], prof[N + 1][N + 1]; int n, m, k, b[N + 1][K + 1], s[N + 1][K + 1]; long long dp[N + 1][N + 1]; void read() { cin >> n >> m >> k; memset(d, 0x3f, sizeof(d)); for (int i = 1; i <= n; ++ i) { //d[i][i] = 0; for (int j = 1; j <= k; ++ j) { cin >> b[i][j] >> s[i][j]; } } for (int i = 1; i <= m; ++ i) { int u, v, w; cin >> u >> v >> w; d[u][v] = min(d[u][v], w); } } bool check(int x) { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { dp[i][j] = prof[i][j] - 1LL * x * d[i][j]; //cerr << dp[i][j] << ' '; } //cerr << '\n'; } for (int k = 1; k <= n; ++ k) { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]); } } } /*cerr << '\n'; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { cerr << dp[i][j] << ' '; } cerr << '\n'; }*/ for (int i = 1; i <= n; ++ i) { if (dp[i][i] >= 0) { return true; } } return false; } void solve() { 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) { prof[i][j] = 0; for (int l = 1; l <= k; ++ l) { if (b[i][l] < 0 || s[j][l] < 0) { continue; } prof[i][j] = max(prof[i][j], s[j][l] - b[i][l]); } } } int low = 1, high = 1e9; while(low <= high) { int mid = (low + high)/2; if (check(mid)) { low = mid + 1; } else { high = mid - 1; } } cout << high; //cout << check(2); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

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

merchant.cpp: In function 'int main()':
merchant.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...