Submission #583202

#	Time	Username	Problem	Language	Result	Execution time	Memory
583202		Jomnoi	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	93 ms	4176 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 105;
const int MAX_K = 1005;
const long long llINF = 1e18 + 7;

long long B[MAX_N][MAX_K], S[MAX_N][MAX_K];
long long dist[MAX_N][MAX_N], dist2[MAX_N][MAX_N];
long long profit[MAX_N][MAX_N];

int main() {
   cin.tie(nullptr)->sync_with_stdio(false);

   int N, M, K;
   cin >> N >> M >> K;

   for(int i = 1; i <= N; i++) {
      for(int j = 1; j <= N; j++) {
         dist[i][j] = llINF;
      }
   }

   for(int i = 1; i <= N; i++) {
      for(int k = 1; k <= K; k++) {
         cin >> B[i][k] >> S[i][k];
      }
   }
   while(M--) {
      int v, w, t;
      cin >> v >> w >> t;
      
      dist[v][w] = t;
   }

   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 i = 1; i <= N; i++) {
      for(int j = 1; j <= N; j++) {
         for(int k = 1; k <= K; k++) {
            if(B[i][k] != -1 and S[j][k] != -1) {
               profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
            }
         }
      }
   }

   int l = 1, r = 1e9, ans = 0;
   while(l <= r) {
      int mid = (l + r) / 2;

      for(int i = 1; i <= N; i++) {
         for(int j = 1; j <= N; j++) {
            dist2[i][j] = llINF;

            if(dist[i][j] != llINF) {
               dist2[i][j] = dist[i][j] * mid - profit[i][j];
            }
         }
      }

      for(int k = 1; k <= N; k++) {
         for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
               dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j]);
            }
         }
      }

      bool hasNegCycle = false;
      for(int i = 1; i <= N; i++) {
         if(dist2[i][i] <= 0) {
            hasNegCycle = true;
         }
      }

      if(hasNegCycle == true) {
         l = mid + 1;
         ans = mid;
      }
      else {
         r = mid - 1;
      }
   }
   cout << ans;
   return 0;
}

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