Submission #1170844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170844		JelalTkm	Travelling Merchant (APIO17_merchant)	C++20	12 / 100	10 ms	1856 KiB

merchant

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e6 + 10;
const int md = 1e9 + 7;
const int INF = 1e12;

vector<int> dijkstra(vector<vector<pair<int, int>>> &g, int start) {
  vector<int> dist(g.size(), INF);
  vector<bool> visited(g.size());
  set<pair<int, int>> q;
  dist[start] = 0;
  q.insert({0, start});

  while (!q.empty()) {
    int v = (*q.begin()).second;
    q.erase(q.begin());
    if (!visited[v])
      for (auto i : g[v]) {
        dist[i.first] = min(dist[i.first], dist[v] + i.second);
        if (!visited[i.first])
          q.insert({dist[i.first], i.first});
      }
    visited[v] = 1;
  }
  return dist;
}

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> b(n + 1, vector<int> (k + 1)), s(n + 1, vector<int> (k + 1));

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= k; j++)
        cin >> b[i][j] >> s[i][j];
    }

    vector<vector<pair<int, int>>> g(n + 1, vector<pair<int, int>> ()), rg(n + 1, vector<pair<int, int>> ());

    for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      g[u].push_back({v, w});
      rg[v].push_back({u, w});
    }

    vector<vector<int>> dist(2, vector<int> ());
    dist[0] = dijkstra(g, 1);
    dist[1] = dijkstra(rg, 1);

    int ans = 0;
    for (int i = 2; i <= n; i++) {
      for (int j = 1; j <= k; j++) {
        if (s[i][j] != -1 && b[1][j] != -1 && (s[i][j] - b[1][j]) > 0) {
          ans = max(ans, (s[i][j] - b[1][j]) / (dist[0][i] + dist[1][i]));
        }
      }
    }

    cout << ans << '\n';
  }

  return 0;
}

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