Submission #722208

#	Time	Username	Problem	Language	Result	Execution time	Memory
722208		YENGOYAN	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	1087 ms	263140 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) {
    d[i][i] = 0;
  }
  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 mn = 2e9, mx = 0;
      int mx = 0;
      for (int t = 0; t < k; ++t) {
        // mn = min(mn, s[i][t]);
        // mx = max(mx, s[j][t]);
        if(s[j][t] == -1 || b[i][t] == -1) continue;
        mx = max(mx, s[j][t] - b[i][t]);
      }
      max_delta[i][j] = max(0, mx);
    }
  }
  vector<vector<int>> new_gp(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i != j) {
        if (d[i][j] != inf) {
          new_gp[i].push_back(j);
        }
      }
    }
  }
  LL ans = 0;
  for (int i = 0; i < n; ++i) {
    priority_queue<pair<LL, int>> pq;
    vector<pair<LL, LL>> dst(n);
    pq.push({0, i});
    while (pq.size()) {
      LL ds = pq.top().first, u = pq.top().second;
      pq.pop();
      if (dst[u].second && LL(dst[u].first / dst[u].second) != ds)
        continue;
      for (int &v : new_gp[u]) {
        if (!dst[v].second ||
            (dst[u].first + max_delta[u][v]) / (dst[u].second + d[u][v]) >
                dst[v].first / dst[v].second) {
          dst[v].first = dst[u].first + max_delta[u][v];
          dst[v].second = dst[u].second + d[u][v];
          pq.push({dst[v].first / dst[v].second, v});
        }
      }
    }
    if(!dst[i].second) {
      continue;
    }

    // cout << i + 1 << " : " << dst[i].first << " " << dst[i].second << "\n";
    ans = max(ans, dst[i].first / dst[i].second);
  }
  cout << ans << "\n";
}

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

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