제출 #838484

#제출 시각아이디문제언어결과실행 시간메모리
838484nonono여행하는 상인 (APIO17_merchant)C++14
100 / 100
59 ms5400 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 1e18; const int mxN = 1005; int N, M, K; int b[mxN][mxN], s[mxN][mxN]; int d[mxN][mxN], dd[mxN][mxN], f[mxN][mxN]; bool find_path(int x) { for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { f[i][j] = dd[i][j] - d[i][j] * x; } } for(int k = 1; k <= N; k ++) { for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { f[i][j] = max(f[i][j], f[i][k] + f[k][j]); } } } int max_Dist = - INF; for(int i = 1; i <= N; i ++) max_Dist = max(max_Dist, f[i][i]); return max_Dist >= 0; } signed main() { #define taskname "" if(fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); cin >> N >> M >> K; for(int i = 1; i <= N; i ++) { for(int j = 1; j <= K; j ++) { cin >> b[i][j] >> s[i][j]; } } for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { d[i][j] = (long long) 1E9; } } for(int i = 1; i <= M; i ++) { int u, v, w; cin >> u >> v >> w; d[u][v] = min(d[u][v], w); } 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 <= K; i ++) { for(int j = 1; j <= N; j ++) { if(b[j][i] == -1) continue ; for(int k = 1; k <= N; k ++) { if(s[k][i] == -1) continue ; dd[j][k] = max(dd[j][k], s[k][i] - b[j][i]); } } } int low = 1, high = (long long) 1E9; while(low <= high) { int mid = (low + high) / 2; if(find_path(mid) == true) low = mid + 1; else high = mid - 1; } cout << low - 1 << "\n"; return 0; }

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

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