제출 #1191916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191916		mannshah1211	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	68 ms	1352 KiB

merchant

/**
 *   author: tourist
 *   created: 25.04.2025 19:27:44
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const long long inf = (long long) 1e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> buy(n, vector<int>(k)), sell(n, vector<int>(k));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      cin >> buy[i][j] >> sell[i][j];
    }
  }
  vector<vector<long long>> profit(n, vector<long long>(n)), dist(n, vector<long long>(n, inf));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int item = 0; item < k; item++) {
        if (buy[i][item] != -1 && sell[j][item] != -1) {
          profit[i][j] = max(profit[i][j], (long long) (sell[j][item] - buy[i][item]));
        }
      }
    }
  }
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    long long t;
    cin >> t;
    --u; --v;
    dist[u][v] = min(dist[u][v], t);
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  auto Check = [&](int mid) {
    vector<vector<long long>> d(n, vector<long long>(n, inf));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (dist[i][j] != inf) {
          d[i][j] = (long long) (mid) * (long long) (dist[i][j]) - profit[i][j];
        }
      }
    }
    for (int k = 0; k < n; k++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
          if (i == j && d[i][j] <= 0) {
            return true;
          }
        }
      }
    }
    return false;
  };
  int low = 0, high = 1e9, ans = -1;
  while (low <= high) {
    int mid = (low + high) >> 1;
    if (Check(mid)) {
      ans = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

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