Submission #655594

#	Time	Username	Problem	Language	Result	Execution time	Memory
655594		bebra	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	107 ms	4140 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define dbg(x) cerr << #x << ": " << x << endl;

const int INF = 1e9;
const int MAX_N = 100;
const int MAX_K = 1000;

int b[MAX_N][MAX_K];
int s[MAX_N][MAX_K];

int max_earn[MAX_N][MAX_N];

int dist[MAX_N][MAX_N];
int new_dist[MAX_N][MAX_N];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for (int v = 0; v < n; ++v) {
        for (int i = 0; i < k; ++i) {
            cin >> b[v][i] >> s[v][i];
        }
    }
    for (int i = 0; i < MAX_N; ++i) {
        for (int j = 0; j < MAX_N; ++j) {
            dist[i][j] = INF;
        }
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int w;
        cin >> w;
        dist[u][v] = w;
    }
    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            for (int i = 0; i < k; ++i) {
                if (s[v][i] == -1 || b[u][i] == -1) continue;
                max_earn[u][v] = max(max_earn[u][v], s[v][i] - b[u][i]);
            }
        }
    }
    for (int w = 0; w < n; ++w) {
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]);
            }
        }
    }
    auto check = [&](int x) {
        if (x == 0) return true;
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                if (dist[u][v] == INF) {
                    new_dist[u][v] = -INF;
                } else {
                    new_dist[u][v] = max_earn[u][v] - x * dist[u][v];
                }
            }
        }
        for (int w = 0; w < n; ++w) {
            for (int u = 0; u < n; ++u) {
                for (int v = 0; v < n; ++v) {
                    if (new_dist[u][w] >= INF || new_dist[w][v] >= INF) {
                        new_dist[u][w] = INF;
                    } else {
                        new_dist[u][v] = max(new_dist[u][v], new_dist[u][w] + new_dist[w][v]);
                    }
                }
            }
        }
        for (int v = 0; v < n; ++v) {
            if (new_dist[v][v] >= 0) {
                return true;
            }
        }
        return false;
    };
    int l = 0;
    int r = 1e9 + 1;
    while (l != r - 1) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l << '\n';
    return 0;
}

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