제출 #945345

#제출 시각아이디문제언어결과실행 시간메모리
945345TAhmed33여행하는 상인 (APIO17_merchant)C++98
0 / 100
103 ms4700 KiB
#include <bits/stdc++.h> using namespace std; typedef __int128 ll; const ll inf = LLONG_MAX / 2; const int MAXN = 100 + 25; ll s[MAXN][1001], b[MAXN][1001]; int n, m, k; ll adj[MAXN][MAXN], adj2[MAXN][MAXN], val[MAXN][MAXN]; bool check (ll x) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { adj2[i][j] = x * min(inf / x, adj[i][j]) - val[i][j]; } } bool flag = 0; for (int l = 1; l <= n; l++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { adj2[i][j] = min(adj2[i][j], adj2[i][l] + adj2[l][j]); } } } for (int i = 1; i <= n; i++) flag |= adj2[i][i] <= 0; return flag; } int main () { cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { int x, y; cin >> x >> y; b[i][j] = x, s[i][j] = y; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { adj[i][j] = inf; } } while (m--) { int a, b, c; cin >> a >> b >> c; adj[a][b] = c; } for (int l = 1; l <= n; l++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { adj[i][j] = min(adj[i][j], adj[i][l] + adj[l][j]); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int l = 1; l <= k; l++) { if (b[i][l] != -1 && s[j][l] != -1) { val[i][j] = max(val[i][j], s[j][l] - b[i][l]); } } } } ll l = 1, r = 1e9, ans = -1; while (l <= r) { ll mid = (l + r) / 2; if (check(mid)) { r = mid - 1; } else { l = mid + 1; } } cout << (long long)(r) << '\n'; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:58:21: warning: unused variable 'ans' [-Wunused-variable]
   58 |  ll l = 1, r = 1e9, ans = -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...