Submission #707258

#	Time	Username	Problem	Language	Result	Execution time	Memory
707258		lto5	Relay Marathon (NOI20_relaymarathon)	C++14	25 / 100	1335 ms	118952 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int64_t INF = 0x3f3f3f3f3f3f3f3f;

template <typename T>
bool minimize(T& a, T b) {
  if (a > b) {
    return a = b, 1;
  }
  return 0;
}

int n, m, k;
vector<pair<int, int>> g[N];
int spec[N];

tuple<int64_t, int, int> best_pair() {
  vector<int64_t> d(n + 1, INF);
  vector<int> head(n + 1, 0);
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  for (int i = 1; i <= n; i++) {
    if (spec[i]) {
      head[i] = i;
      d[i] = 0;
      pq.emplace(d[i], i);
    }
  }
  while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (d[u] != du) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        head[v] = head[u];
        pq.emplace(d[v], v);
      }
    }
  }
  int64_t best = INF;
  int best_u = -1, best_v = -1;
  for (int u = 1; u <= n; u++) {
    for (auto [v, w] : g[u]) {
      if (d[u] != INF && d[v] != INF && head[u] != head[v]) {
        if (minimize(best, d[u] + d[v] + w)) {
          best = d[u] + d[v] + w;
          best_u = head[u];
          best_v = head[v];
        }
      }
    }
  }
  return {best, best_u, best_v};
}

pair<int64_t, int> nearest_spec(int s) {
  vector<int64_t> d(n + 1, INF);
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  d[s] = 0;
  pq.emplace(d[s], s);
  while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (d[u] != du) {
      continue;
    }
    if (spec[u]) {
      return {d[u], u};
    }
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.emplace(d[v], v);
      }
    }
  }
  return {INF, 0};
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
#define task "a"
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  cin >> n >> m >> k;
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  while (k--) {
    int u;
    cin >> u;
    spec[u] = 1;
  }
  // {a, b, c, d}
  // d(a, b) + d(c, d) min
  // (x, y) = min pair
  /* {x, y} is subset of {a, b, c, d}
   * x != {a, b, c, d} or y != {a, b, c, d} : change something by {x, y} and get better answer
   */

  auto [min_d, x, y] = best_pair();
  int64_t best = INF;
  spec[x] = spec[y] = 0;
  // a = x, b = y
  {
    auto [second_min_d, z, t] = best_pair();
    minimize(best, min_d + second_min_d);
  }
  // a = x, c = y
  {
    auto [nearest_a, z] = nearest_spec(x);
    spec[z] = 0;
    auto [nearest_b, t] = nearest_spec(y);
    minimize(best, nearest_a + nearest_b);
  }
  cout << best;
  return 0;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'std::tuple<long int, int, int> best_pair()':
RelayMarathon.cpp:31:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     auto [du, u] = pq.top();
      |          ^
RelayMarathon.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [v, w] : g[u]) {
      |               ^
RelayMarathon.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto [v, w] : g[u]) {
      |               ^
RelayMarathon.cpp: In function 'std::pair<long int, int> nearest_spec(int)':
RelayMarathon.cpp:66:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     auto [du, u] = pq.top();
      |          ^
RelayMarathon.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for (auto [v, w] : g[u]) {
      |               ^
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:112:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |   auto [min_d, x, y] = best_pair();
      |        ^
RelayMarathon.cpp:117:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |     auto [second_min_d, z, t] = best_pair();
      |          ^
RelayMarathon.cpp:122:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     auto [nearest_a, z] = nearest_spec(x);
      |          ^
RelayMarathon.cpp:124:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     auto [nearest_b, t] = nearest_spec(y);
      |          ^
RelayMarathon.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 25 / 25
• Subtask 4: 0 / 58