Submission #561144

#	Time	Username	Problem	Language	Result	Execution time	Memory
561144		Sweezy	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	107 ms	4276 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int inf = 2e9 + 7;

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> buy(n, vector<int> (k)), sell(n, vector<int> (k)), d(n, vector<int> (n, inf)), profit(n, vector<int> (n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      cin >> buy[i][j] >> sell[i][j];
    }
  }
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    d[u][v] = c;
  }
  for (int w = 0; w < n; w++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j] = min(d[i][j], d[i][w] + d[w][j]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      for (int w = 0; w < k; w++) {
        if (buy[i][w] != -1 && sell[j][w] != -1) {
          profit[i][j] = max(profit[i][j], sell[j][w] - buy[i][w]);
        }
      }
    }
  }
  int l = 0, r = inf;
  while (l + 1 < r) {
    int m = (l + r) / 2;
    vector<vector<int>> edges(n, vector<int> (n, inf));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        edges[i][j] = min(edges[i][j], m * d[i][j] - profit[i][j]);
      }
    }
    auto cost = edges;
    for (int w = 0; w < n; w++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          cost[i][j] = min(cost[i][j], cost[i][w] + cost[w][j]);
        }
      }
    }

    bool cycle = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i == j) continue;
        cycle |= (cost[i][j] + edges[j][i]) <= 0;
      }
    }

    if (cycle) {
      l = m;
    } else {
      r = m;
    }
  }

  cout << l;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

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