Submission #722291

#	Time	Username	Problem	Language	Result	Execution time	Memory
722291		YENGOYAN	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	97 ms	3492 KiB

merchant

/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;

vector<int> dx = {1, 0, 0, -1, 1, 1, -1, -1};
vector<int> dy = {0, 1, -1, 0, 1, -1, 1, -1};

int n, m, k;

void solve() {
  cin >> n >> m >> k;
  vector<vector<int>> s(n, vector<int>(k)), b(n, vector<int>(k));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < k; ++j) {
      cin >> b[i][j] >> s[i][j];
    }
  }
  vector<vector<pair<int, int>>> gp(n);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    gp[--u].push_back({--v, w});
  }
  vector<vector<LL>> d(n, vector<LL>(n, inf));
  for (int i = 0; i < n; ++i) {
    priority_queue<pair<LL, int>> pq;
    pq.push({0, i});
    while (pq.size()) {
      LL ds = -pq.top().first, u = pq.top().second;
      pq.pop();
      if (ds > d[i][u])
        continue;
      for (pair<int, int> &v : gp[u]) {
        if (ds + v.second < d[i][v.first]) {
          d[i][v.first] = ds + v.second;
          pq.push({-d[i][v.first], v.first});
        }
      }
    }
  }
  vector<vector<int>> max_delta(n, vector<int>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int mx = 0;
      for (int t = 0; t < k; ++t) {
        if(s[j][t] == -1 || b[i][t] == -1) continue;
        mx = max(mx, s[j][t] - b[i][t]);
      }
      max_delta[i][j] = mx;
    }
  }
  vector<vector<LL>> d1 = d;
  function<void()> max_path = [&](){
    for(int k = 0; k < n; ++k){
      for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
          d1[i][j] = max(d1[i][j], d1[i][k] + d1[k][j]);
        }
      }
    }
  };
  LL l = 0, r = 2e9;
  while(l + 1 < r){
    LL mid = (l + r) / 2;
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j){
        d1[i][j] = max_delta[i][j] - mid * min(inf / mid, d[i][j]);
      }
    }
//    cout << mid << "\n";
    max_path();
    for(int i = 0; i < n; ++i){
      if(d1[i][i] >= 0) {
        l = mid;
      }
    }
    if(l != mid) {
      r = mid;
    }
  }
  cout << l << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // int t; cin >> t; while (t--)
  solve();
}

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