Submission #408268

#	Time	Username	Problem	Language	Result	Execution time	Memory
408268		dannyboy20031204	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	163 ms	3360 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll inf = 1ll << 60;
const int N = 101, K = 1001;
int b[N][K], s[N][K], c[N][N];
ll t[N][N];
int n, m, k;
bool check(ll mid){
     if (mid == 0) return true;
     ll mi[N][N];
     for (int i = 1; i <= n; i++){
          for (int j = 1; j <= n; j++){
               if (t[i][j] < inf / mid) mi[i][j] = t[i][j] * mid - c[i][j];
               else mi[i][j] = inf;
          }
     }
     for (int i = 1; i <= n; i++){
          for (int u = 1; u <= n; u++){
               for (int v = 1; v <= n; v++){
                    mi[u][v] = min(mi[u][v], mi[u][i] + mi[i][v]);
               }
          }
     }
     for (int i = 1; i <= n; i++) if (mi[i][i] <= 0) return true;
     return false;
}
int main(){
     ios::sync_with_stdio(0), cin.tie(0);
     cin >> n >> m >> k;
     for (int i = 1; i <= n; i++){
          for (int j = 0; j < k; j++) cin >> b[i][j] >> s[i][j];
     }
     for (auto &i : t) for (ll &j : i) j = inf; //!!!
     for (int i = 0; i < m; i++){
          int u, v, _t;
          cin >> u >> v >> _t;
          t[u][v] = _t;
     }
     for (int i = 1; i <= n; i++){
          for (int j = 1; j <= n; j++){
               c[i][j] = 0;
               for (int _k = 0; _k < k; _k++)
                    if (~s[j][_k] and ~b[i][_k]) c[i][j] = max(c[i][j], s[j][_k] - b[i][_k]);
          }
     }
     for (int i = 1; i <= n; i++){
          for (int u = 1; u <= n; u++){
               for (int v = 1; v <= n; v++){
                    t[u][v] = min(t[u][v], t[u][i] + t[i][v]);
               }
          }
     }
     ll l = 0, r = inf;
     while (l < r){
          ll mid = l + r >> 1;
          if (check(mid)) l = mid + 1;
          else r = mid;
     }
     cout << l - 1 << '\n';
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |           ll mid = l + r >> 1;
      |                    ~~^~~

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