Submission #568504

#	Time	Username	Problem	Language	Result	Execution time	Memory
568504		Ooops_sorry	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	75 ms	3412 KiB

merchant

#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;
}

Compilation message (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);
      |                   ^

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34