Submission #1182437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182437		totoro	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	41 ms	1856 KiB

merchant

#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

struct Edge {
    int to;
    long long length, profit;
};

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<long long>> b(n, std::vector<long long>(k)), s(n, std::vector<long long>(k));
    for (int i = 0; i < n; ++i) {
        for (int item = 0; item < k; ++item) std::cin >> b[i][item] >> s[i][item];
    }
    std::vector<std::vector<Edge>> adj(n);
    while (m--) {
        int u, v;
        long long t;
        std::cin >> u >> v >> t;
        --u, --v;
        adj[u].emplace_back(v, t, 0);
    }
    std::vector<std::vector<long long>> shortestPath(n, std::vector<long long>(n));
    for (int i = 0; i < n; ++i) {
        std::priority_queue<std::pair<long long, int>> q;
        std::vector<int> seen(n);
        q.emplace(0, i);
        while (!q.empty()) {
            auto [d, node] = q.top();
            q.pop();
            if (seen[node]) continue;
            shortestPath[i][node] = -d;
            seen[node] = true;
            for (auto e : adj[node]) {
                q.emplace(d - e.length, e.to);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int f = 0; f < n; ++f) {
            if (i == f) continue;
            long long max = 0;
            for (int item = 0; item < k; ++item) {
                if (b[i][item] == -1 || s[i][item] == -1) continue;
                max = std::max(max, s[f][item] - b[i][item]);
            }
            if (max) {
                adj[i].emplace_back(f, shortestPath[i][f], max);
            }
        }
    }
    exit(0);
    long long max = 0;
    for (int i = 0; i < n; ++i) {
        std::queue<std::tuple<int, long long, long long, int>> q;
        q.emplace(i, 0, 0, 0);
        while (!q.empty()) {
            auto [node, dist, profit, littledist] = q.front();
            q.pop();
            if (littledist > n) break;
            if (node == i && dist) {
                max = std::max(max, profit / dist);
            }
            for (auto e : adj[node]) {
                q.emplace(e.to, dist + e.length, profit + e.profit, littledist + 1);
            }
        }
    }
    std::cout << max << '\n';
    return 0;
}

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