Submission #1202180

#TimeUsernameProblemLanguageResultExecution timeMemory
1202180totoroTravelling Merchant (APIO17_merchant)C++20
0 / 100
72 ms2120 KiB
#include <iostream> #include <queue> #include <tuple> #include <utility> #include <vector> const long long INF = 1e18; 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[f][item] == -1) continue; max = std::max(max, s[f][item] - b[i][item]); } if (max) { adj[i].emplace_back(f, shortestPath[i][f], max); } } } long long lo = 0, hi = 2e9; while (lo < hi) { long long mid = (lo + hi + 1) / 2; std::vector<std::vector<long long>> floyd(n, std::vector<long long>(n, -INF)); // longest path for (int i = 0; i < n; ++i) { for (auto [to, dist, profit] : adj[i]) floyd[i][to] = profit - mid * dist; } for (int kk = 0; kk < n; ++kk) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { floyd[i][j] = std::max(floyd[i][j], floyd[i][kk] + floyd[kk][j]); } } } bool exists = false; for (int i = 0; i < n; ++i) exists |= (floyd[i][i] >= 0); if (exists) { lo = mid; } else { hi = mid - 1; } } std::cout << lo << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...