Submission #655497

#	Time	Username	Problem	Language	Result	Execution time	Memory
655497		bebra	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	29 ms	2124 KiB

merchant

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

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

const int INF = 1e13;
const int MAX_N = 100;
const int MAX_K = 1000;
int cost[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
int dist1[MAX_N][MAX_N];
int eff[MAX_N][MAX_N];
int b[MAX_N][MAX_K];
int s[MAX_N][MAX_K];
int max_earn[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;
            dist1[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;
        dist1[u][v] = w;
    }
    for (int u = 0; u < n; ++u) {
        dist[u][u] = 0;
        dist1[u][u] = 0;
        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) {
                if (u == w && w == v) continue;
                dist1[u][v] = min(dist1[u][v], dist1[u][w] + dist1[w][v]);
                // cost[u][w] must be compatible with dist[u][w]
                int curr_eff = (cost[u][w] + max_earn[w][v]) / (dist[u][w] + dist1[w][v]);
                if (curr_eff >= eff[u][v]) {
                    dist[u][v] = dist[u][w] + dist1[w][v];
                    cost[u][v] = cost[u][w] + max_earn[w][v];
                    eff[u][v] = curr_eff;
                }
            }
        }
    }
    cout << eff[0][0] << '\n';
    return 0;
}

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