Submission #408200

#	Time	Username	Problem	Language	Result	Execution time	Memory
408200		dannyboy20031204	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	1085 ms	1236 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];
ll t[N][N];
int n, m, k;
bool check(ll mid){
     ll mi[N][N];
     for (int i = 1; i <= n; i++){
          for (int j = 1; j <= n; j++){
               mi[i][j] = inf;
               for (int _k = 0; _k < k; _k++){
                    if (b[i][_k] > 0 and s[j][_k] > 0 and t[i][j] < inf){
                         mi[i][j] = min(mi[i][j], mid * t[i][j] - (s[j][_k] - b[i][_k]));
                    }
                    if (t[i][j] < inf){
                         mi[i][j] = min(mi[i][j], mid * t[i][j]);
                    }
                    //cout << i << ' ' << j << ' ' << mi[i][j]<< '\n';
               }
          }
     }
     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 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]);
               }
          }
     }
     //check(2);
     //return 0;
     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:58:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |           ll mid = l + r >> 1;
      |                    ~~^~~

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