Submission #310163

#	Time	Username	Problem	Language	Result	Execution time	Memory
310163		quocnguyen1012	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	129 ms	1272 KiB

merchant

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define ar array
#define eb emplace_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 105, maxk = 1005, inf = 1e9;

int N, M, K;
int dist[maxn][maxn], op[maxn][maxn];
int buy[maxk][maxn], sell[maxk][maxn];
ll go[maxn][maxn];

bool check(int lim) {
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      go[i][j] = -inf;
      if (dist[i][j] == inf)
        continue;
      go[i][j] = op[i][j] - (ll)lim * dist[i][j];
    }
  }
  for (int k = 1; k <= N; ++k) {
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= N; ++j) {
        go[i][j] = max(go[i][j], go[i][k] + go[k][j]);
        if (go[i][j] >= inf)
          go[i][j] = inf;
      }
    }
  }

  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      if (go[i][j] + go[j][i] >= 0)
        return true;
    }
  }
  return false;
}


signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL

  cin >> N >> M >> K;
  for (int i = 1;  i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      dist[i][j] = inf;
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= K; ++j) {
      cin >> buy[j][i] >> sell[j][i];
    }
  }
  while (M--) {
    int u, v, w; cin >> u >> v >> w;
    dist[u][v] = min(dist[u][v], w);
  }

  for (int k = 1; k <= N; ++k) {
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= N; ++j) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  for (int u = 1; u <= N; ++u) {
    for (int v = 1; v <= N; ++v) {
      for (int item = 1; item <= K; ++item) {
        if (buy[item][u] != -1 && sell[item][v] != -1) {
          op[u][v] = max(op[u][v], -buy[item][u] + sell[item][v]);
        }
      }
    }
  }

  int lo = 1, hi = 1e9, mid;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (check(mid)) lo = mid + 1;
    else hi = mid - 1;
  }
  cout << hi;
}

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