Submission #1261177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261177		LucaLucaM	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1095 ms	2024 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const ll INF = 1e18;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n, m, k;
  std::cin >> n >> m >> k;

  std::vector<std::vector<int>> buy(n, std::vector<int>(k + 1));
  std::vector<std::vector<int>> sell(n, std::vector<int>(k + 1));
  
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= k; j++) {
      std::cin >> buy[i][j] >> sell[i][j];
    }
  }

  std::vector<std::vector<std::pair<int, int>>> g(n);
  std::vector<std::vector<std::pair<int, int>>> gg(n);
  for (int i = 0; i < m; i++) {
    int u, v, t;
    std::cin >> u >> v >> t;
    u--, v--;
    g[u].push_back({v, t});
    gg[v].push_back({u, t});
  }
  
  auto check = [&](int root, int mid) {
    std::vector<std::vector<ll>> d(n, std::vector<ll>(k + 1, +INF));
    d[root][0] = 0;
    bool repeat = true;
    for (int _ = 0; _ < 100; _++) {
      repeat = false;
      for (int u = 0; u < n; u++) {
        for (int i = 1; i <= k; i++) {
          if (sell[u][i] != -1 && d[u][i] + -sell[u][i] < d[u][0]) {
            d[u][0] = d[u][i] - sell[u][i];
            repeat = true;
          }
          if (buy[u][i] != -1 && d[u][0] + buy[u][i] < d[u][i]) {
            d[u][i] = d[u][0] + buy[u][i];
            repeat = true;
          }
        }
        for (int i = 0; i <= k; i++) {
          for (auto [v, t] : g[u]) {
            ll w = (ll) mid * t;
            if (d[u][i] + w < d[v][i]) {
              d[v][i] = d[u][i] + w;
              repeat = true;
            }
          }
        }
      }
    }
    if (repeat) {
      return true;
    }
    for (auto [u, t] : gg[root]) {
      ll w = (ll) mid * t;
      if (d[u][0] + w <= 0) {
        return true;
      }
      for (int i = 1; i <= k; i++) {
        if (sell[root][i] != -1 && d[u][i] + w + -sell[root][i] <= 0) {
          return true;
        }
      }
    }
    return false;
  };

  int answer = 0;
  for (int root = 0; root < n; root++) {
    if (check(root, answer)) {
      int l = answer, r = 1e9;
      while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(root, mid)) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      answer = r;
    }
  }

  std::cout << answer;
  
  return 0;
}

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