Submission #1314655

#TimeUsernameProblemLanguageResultExecution timeMemory
1314655joshjuiceRelay Marathon (NOI20_relaymarathon)C++20
100 / 100
1402 ms160896 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define all(a) a.begin(), a.end()
#define ppf pop_front
#define ppb pop_back
#define pf push_front
#define pb push_back
#define fr first
#define sc second
#define ii pair<int, int>
#define iii tuple<int, int, int>
#define vc vector
#define sz(a) a.size()
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)
#define setval(arr, x) memset(arr, x, sizeof(arr))

template<typename T>
using vv = vc<vc<T>>;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5+5;
const int INF = 1e18;

int n, m, k;
vc<ii> adj[N];
vc<int> special;

vc<int> dijkstra(int src, const vc<bool> &skip) {
  vc<int> dist(n+1, INF);
  vc<bool> visited(n+1, 0);
  priority_queue<ii, vc<ii>, greater<>> pq;
  dist[src] = 0;
  pq.push({0, src});
  while (sz(pq)) {
    int u = pq.top().sc;
    pq.pop();
    if (visited[u]) continue;
    visited[u] = 1;
    for (auto &[v, w] : adj[u]) {
      if (skip[v]) continue;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push({dist[v], v});
      }
    }
  }
  return dist;
}

iii nsp(const vc<bool> &skip) {
  vc<int> dist(n+1, INF);
  vc<int> source(n+1, -1);
  vc<bool> visited(n+1, 0);
  priority_queue<ii, vc<ii>, greater<>> pq;
  for (int u : special) {
    if (skip[u]) continue;
    dist[u] = 0;
    source[u] = u;
    pq.push({0, u});
  }
  while (sz(pq)) {
    int u = pq.top().sc;
    pq.pop();
    if (visited[u]) continue;
    visited[u] = 1;
    for (auto &[v, w] : adj[u]) {
      if (skip[v]) continue;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        source[v] = source[u];
        pq.push({dist[v], v});
      }
    }
  }
  int best = INF;
  int a = -1, b = -1;
  rep(u, 1, n+1) {
    if (skip[u]) continue;
    for (auto &[v, w] : adj[u]) {
      if (skip[v]) continue;
      if (source[u] != source[v] && dist[u] != INF && dist[v] != INF) {
        int tot = dist[u] + w + dist[v];
        if (tot < best) {
          best = tot;
          a = source[u];
          b = source[v];
        }
      }
    }
  }
  return {a, b, best};
}

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m >> k;
  rep(i, 0, m) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].pb({v, w});
    adj[v].pb({u, w});
  }
  special.resize(k);
  vc<bool> skip(n+1, 0);
  rep(i, 0, k) cin >> special[i];
  auto [x1, y1, d1] = nsp(skip);
  auto dx1 = dijkstra(x1, skip);
  auto dy1 = dijkstra(y1, skip);
  int ans = INF;
  int c1 = -1, c2 = -1;
  for (int u : special) {
    if (u == x1 || u == y1) continue;
    if (c1 == -1 || dy1[u] <= dy1[c1]) { c2 = c1; c1 = u; }
    else if (c2 == -1 || dy1[u] < dy1[c2]) c2 = u;
  }
  if (dx1[c1] != INF && dy1[c2] != INF) mnto(ans, dx1[c1] + dy1[c2]);
  for (int x2 : special) {
    if (x2 == x1 || x2 == y1 || x2 == c1) continue;
    if (dx1[x2] != INF && dy1[c1] != INF) mnto(ans, dx1[x2] + dy1[c1]);
  }
  skip[x1] = skip[y1] = 1;
  auto [x3, y3, d2] = nsp(skip);
  if (d1 != INF && d2 != INF) mnto(ans, d1+d2);
  cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...