제출 #741547

#제출 시각아이디문제언어결과실행 시간메모리
741547406여행하는 상인 (APIO17_merchant)C++17
100 / 100
95 ms2920 KiB
#include "bits/stdc++.h" #define int long long using namespace std; const long long INF = 1ll << 30; const long long INF2 = 1ll << 60; const int N = 100 + 5; const int M = 1e4 + 5; const int K = 1000 + 5; int d[N][N], n, k, U[M], V[M], W[M], B[N][K], S[N][K], P[N][N], e, D[N][N]; void floyd(int d[N][N]) { for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } bool check(int O) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = O * min(D[i][j], INF2 / O) - P[i][j]; floyd(d); for (int i = 0; i < n; i++) if (d[i][i] <= 0) return true; return false; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> e >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) cin >> B[i][j] >> S[i][j]; } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) D[i][j] = INF2; for (int i = 0; i < e; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; D[u][v] = w; } floyd(D); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int l = 0; l < k; l++) if (B[i][l] != -1 && S[j][l] != -1) P[i][j] = max(P[i][j], -B[i][l] +S[j][l]); int l = 0, r = INF; while (r - l > 1) { int m = l + r >> 1; if (check(m)) l = m; else r = m; } cout << l; return 0; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int m = l + r >> 1;
      |           ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...