Submission #261651

#	Time	Username	Problem	Language	Result	Execution time	Memory
261651		Haunted_Cpp	Relay Marathon (NOI20_relaymarathon)	C++17	42 / 100	2208 ms	71960 KiB

RelayMarathon

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const int MAX_N = 1e5 + 5;
const int INF = 1e9 + 5;

vector<vector<pair<int, int>>> g(MAX_N);

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int st, et, w;
    cin >> st >> et >> w;
    --st; --et;
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  vector<bool> is_special(n);
  for (int i = 0; i < k; i++) {
    int foo;
    cin >> foo;
    --foo;
    is_special[foo] = true;
  }
  int res = 0;
  int add = 0;
  auto Dijkstra = [&](bool basic_graph) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dist(n, INF);
    vector<int> root(n, -1);
    vector<pair<int, int>> closest_vertex(n, {INF, -1});
    for (int i = 0; i < n; i++) {
      if (is_special[i]) {
        dist[i] = 0;
        root[i] = i;
        pq.push({dist[i], i});
      }
    }
    while(!pq.empty()) {
      int node = pq.top().second;
      int w = pq.top().first;
      pq.pop();
      if (w != dist[node]) continue;
      for (auto to : g[node]) {
        if (root[to.first] != -1 && root[to.first] != root[node]) {
          pair<int, int> best_way = {dist[node] + to.second + dist[to.first], root[to.first]};
          closest_vertex[root[node]] = min(closest_vertex[root[node]], best_way);
        }
        if (dist[to.first] > dist[node] + to.second) {
          dist[to.first] = dist[node] + to.second;
          root[to.first] = root[node];
          pq.push({dist[to.first], to.first});
        }
      }
    }
    int mn = 1e9;
    for (int i = 0; i < n; i++) {
      if (!is_special[i]) continue;
      mn = min(mn, closest_vertex[i].first);
    }
    add = mn;
    if (!basic_graph) {
      for (int i = 0; i < n; i++) {
        if (!is_special[i]) continue;
        if (closest_vertex[i].first == mn) {
          res += closest_vertex[i].first;
          is_special[i] = false;
          is_special[closest_vertex[i].second] = false;
          break;
        }
      }
    }
    return closest_vertex;
  };
  if (n > 500) {
    Dijkstra(false);
    Dijkstra(false);
    cout << res << '\n';
  } else {
    int mn = 1e9;
    vector<pair<int, int>> dist = Dijkstra(true);
    for (int i = 0; i < n; i++) {
      if (!is_special[i]) continue;
      if (dist[i].second == -1) continue;
      assert(is_special[dist[i].second]);
      int cur = dist[i].first;
      is_special[i] = false;
      is_special[dist[i].second] = false;
      add = 0;
      Dijkstra(true);
      cur += add;
      mn = min(mn, cur);
      is_special[i] = true;
      is_special[dist[i].second] = true;
    }
    cout << mn << '\n';
  }
  return 0;
}

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