제출 #568504

#제출 시각아이디문제언어결과실행 시간메모리
568504Ooops_sorry여행하는 상인 (APIO17_merchant)C++14
100 / 100
75 ms3412 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define ld double #define ll long long mt19937 rnd(51); const int N = 110, K = 1010, INF = 1e9; ll d[N][N]; int b[N][K], s[N][K], mx[N][N], n, m, k; vector<pair<int,ll>> g[N]; bool solve(int mid) { for (int i = 0; i < N; i++) g[i].clear(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) { g[i].pb({j, (ll)mx[i][j] - mid * d[i][j]}); } } } vector<ll> d(n); vector<bool> a(n, 1); for (int i = 0; i <= n; i++) { bool ok = 0; vector<bool> b(n); for (int j = 0; j < n; j++) { if (!a[j]) continue; for (auto to : g[j]) { if (d[j] + to.second >= d[to.first]) { d[to.first] = d[j] + to.second; ok = 1; b[to.first] = 1; } } } swap(a, b); if (i == n) return ok; } } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d[i][j] = INF; } d[i][i] = 0; } 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++) { mx[i][j] = 0; for (int f = 0; f < k; f++) { if (b[i][f] == -1 || s[j][f] == -1) continue; mx[i][j] = max(mx[i][j], s[j][f] - b[i][f]); } } } for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; d[a][b] = c; } 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]); } } } int l = 0, r = INF; while (r - l > 1) { int mid = (r + l) / 2; if (solve(mid)) { l = mid; } else { r = mid; } } cout << l << endl; return 0; }

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

merchant.cpp: In function 'bool solve(int)':
merchant.cpp:25:19: warning: control reaches end of non-void function [-Wreturn-type]
   25 |     vector<ll> d(n);
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...