제출 #1226359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226359		kunzaZa183	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	289 ms	2228 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
signed main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> status(n, vector<int>(2 * k));
  for (auto &a : status) {
    for (auto &b : a)
      cin >> b;
  }

  const int bign = 1e9;
  vector<vector<int>> adjmat(n, vector<int>(n, bign));
  for (int i = 0; i < m; i++) {
    int a, b, t;
    cin >> a >> b >> t;
    a--, b--;
    adjmat[a][b] = t;
  }
  for (int i = 0; i < n; i++)
    adjmat[i][i] = 0;

  for (int rounds = 0; rounds < 6; rounds++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
          if (adjmat[i][k] != bign && adjmat[k][j] != bign)
            adjmat[i][j] = min(adjmat[i][j], adjmat[i][k] + adjmat[k][j]);

  vector<vector<int>> maxp(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int in = 0; in < k; in++) {
        if (status[i][in * 2] != -1 && status[j][in * 2 + 1] != -1)
          maxp[i][j] =
              max(maxp[i][j], status[j][in * 2 + 1] - status[i][in * 2]);
      }
    }
  }

  ll l = 0, r = bign, ans = 0;

  const int biggern = 1e18;
  while (l <= r) {
    int mid = (l + r) / 2;
    vector<vector<int>> mat(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++)
        mat[i][j] = mid * adjmat[i][j] - maxp[i][j];
    }
    for (int i = 0; i < n; i++)
      mat[i][i] = biggern;

    for (int rounds = 0; rounds < 6; rounds++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          for (int k = 0; k < n; k++)
            mat[i][j] = min(mat[i][j], max(-biggern, mat[i][k] + mat[k][j]));

    for (int i = 0; i < n; i++)
      if (mat[i][i] <= 0) {
        l = mid + 1;
        ans = mid;
        goto A;
      }
    r = mid - 1;
  A:;
  }
  cout << ans << "\n";
}

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