Submission #1164508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164508		baldwin_huang	Travelling Merchant (APIO17_merchant)	C++20	12 / 100	10 ms	1088 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

struct product {
    int buy;
    int sell;
};

struct road {
    int destination;
    int travel_time;
};

const int INF = 1e9;
int n, m, k;

vector< vector<int> > shortest_distance(100 + 1, vector<int>(100 + 1, INF));

void floyd_warshall(vector< vector<road> > &graph) {
    for (int i = 1; i <= n; i++) {
        shortest_distance[i][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (auto &j: graph[i]) {
            shortest_distance[i][j.destination] = j.travel_time;
        }
    }

    // The node that goes in between.
    for (int k = 1; k <= n; k++) {
        // The source node.
        for (int i = 1; i <= n; i++) {
            // The destination node.
            for (int j = 1; j <= n; j++) {
                if ((shortest_distance[i][k] + shortest_distance[k][j]) < shortest_distance[i][j]) {
                    shortest_distance[i][j] = (shortest_distance[i][k] + shortest_distance[k][j]);
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    // products[market][product number];
    vector< vector<product> > products(n + 1, vector<product>(k + 1));
    vector< vector<road> > graph(n + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            int b, s;
            cin >> b >> s;
            products[i][j].buy = b;
            products[i][j].sell = s;
        }
    }

    for (int i = 1; i <= m; i++) {
        int v, w, t;
        cin >> v >> w >> t;
        graph[v].push_back({w, t});
    }

    floyd_warshall(graph);

    // Go throught every product and market.
    // Iterate through every product.
    int most_efficient = 0;
    for (int i = 1; i <= k; i++) {
        // Iterate through every market.
        for (int j = 2; j <= n; j++) {
            int profit = products[j][i].sell - products[1][i].buy;
            if (profit < 0) {
                continue;
            }
            int time = shortest_distance[1][j] + shortest_distance[j][1];
            most_efficient = max(most_efficient, (profit / time));
        }
    }

    cout << most_efficient << '\n';

    return 0;
}

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