JOI 本選 2012 E - JOI 国のお祭り事情(Festivals in JOI Kingdom) 解説

問題

onlinejudge.u-aizu.ac.jp

前提

• ダイクストラ法
• クラスカル法
• 最近共通祖先（Lowest Common Ancestor）

解説

ダイクストラ法、クラスカル法（的な発想）、Lowest Common Ancestor、3つ基本アルゴリズムの合わせ技で解ける良問。

ざっと他の人の解説を見てみたところ、並行二分探索による解説が多かったので、3つのアルゴリズムを使う解説を載せておく。

（１）ダイクストラ法

まず最初に各頂点に、自身から最も近いお祭りまでの距離を記録する => ダイクストラ法。（辺にコストがあるためBFSだとTLEになることに注意する）

（２）クラスカル法

（１）を元に、辺のコストを両端の2頂点のお祭りまでの距離のminとするグラフを作る。このグラフから、ある経路を通った時の祭りまでの距離の最小は通った辺のコストの最小に等しくなる。

このグラフを更に辺のコストの大きい順に取っていくことで全域木を作ることを考える。（ここがクラスカル法的な発想）

全域木になった時点で任意の2頂点の行き来は可能である。そして、この過程で全域木を作り残った辺を追加しても、ある頂点間のお祭りまでの距離が改善すること（大きくなること）がない。よって、この全域木における2頂点間のコストの最小がお祭りまでの距離になる。

（３）Lowest Common Ancestor

最後に、2頂点間の経路は(s, t)のLCAを求めて、s, t それぞれからLCAに向けて頂点を見ていけば無駄なく探索を行える。これはダブリングのテーブルがあれば行える。

（３）における2頂点間のお祭りまでの距離の最小値を求める処理がボトルネックで、O(n * q) となるが、制約から N ≤ 5000, Q ≤ 5000 のいずれかを満たすため間に合う。

実装

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)

template <class T> inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int INF = 1e9 + 10;

class UnionFind {
private:
  vector<int> parent;

public:
  UnionFind(int n) { parent = vector<int>(n, -1); }

  int root(int a) {
    if (parent[a] < 0)
      return a;
    return parent[a] = root(parent[a]);
  }

  int size(int a) { return -parent[root(a)]; }

  bool connect(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
      return false;
    }
    if (size(a) < size(b))
      swap(a, b);
    parent[a] += parent[b];
    parent[b] = a;
    return true;
  }

  bool is_same(int a, int b) { return root(a) == root(b); }
};

class LCA {
private:
  int root;
  int k;
  vector<vector<int>> dp;
  vector<int> depth;
  vector<int> dist;

public:
  LCA(const vector<vector<int>> &_G, vector<int> _dist, const int _root = 0) {
    int n = _G.size();
    dist = _dist;
    root = _root;
    k = 1;
    int nibeki = 2;
    while (nibeki < n) {
      nibeki <<= 1;
      k++;
    }
    dp = vector<vector<int>>(k + 1, vector<int>(n, -1));
    depth.resize(n);
    function<void(int, int)> _dfs = [&](int v, int p) {
      dp[0][v] = p;
      for (auto nv : _G[v]) {
        if (nv == p)
          continue;
        depth[nv] = depth[v] + 1;
        _dfs(nv, v);
      }
    };
    _dfs(root, -1);
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < n; j++) {
        if (dp[i][j] == -1)
          continue;
        dp[i + 1][j] = dp[i][dp[i][j]];
      }
    }
  }

  /// get LCA
  int get(int u, int v) {
    if (depth[u] < depth[v])
      swap(u, v);
    if (depth[u] != depth[v]) {
      long long d = depth[u] - depth[v];
      for (int i = 0; i < k; i++)
        if ((d >> i) & 1)
          u = dp[i][u];
    }
    if (u == v)
      return u;

    for (int i = k; i >= 0; i--) {
      if (dp[i][u] != dp[i][v]) {
        u = dp[i][u], v = dp[i][v];
      }
    }
    return dp[0][u];
  }

  int get_min_cost(int u, int v) {
    int lca = get(u, v);
    int min_cost = dist[lca];
    while (u != lca) {
      chmin(min_cost, dist[u]);
      u = dp[0][u];
    }
    while (v != lca) {
      chmin(min_cost, dist[v]);
      v = dp[0][v];
    }
    return min_cost;
  }
};

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  // input
  int n, m, k, q;
  cin >> n >> m >> k >> q;
  vector<int> a(k);
  vector<vector<pair<int, int>>> G(n);
  rep(i, m) {
    int a, b, l;
    cin >> a >> b >> l;
    a--, b--;
    G[a].emplace_back(b, l);
    G[b].emplace_back(a, l);
  }

  // dijkstra
  vector<int> dist(n, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
  rep(i, k) {
    int f;
    cin >> f;
    f--;
    dist[f] = 0;
    que.emplace(0, f);
  }

  while (!que.empty()) {
    int c, v;
    tie(c, v) = que.top();
    que.pop();
    if (c > dist[v])
      continue;
    for (auto p : G[v]) {
      int nv, nc;
      tie(nv, nc) = p;
      if (chmin(dist[nv], dist[v] + nc)) {
        que.emplace(dist[nv], nv);
      }
    }
  }

  // kruskal
  vector<tuple<int, int, int>> edge;
  rep(v, n) for (auto p : G[v]) {
    int nv, c;
    tie(nv, c) = p;
    edge.emplace_back(min(dist[v], dist[nv]), v, nv);
  }
  sort(edge.rbegin(), edge.rend());

  auto uf = UnionFind(n);
  vector<vector<int>> tree(n);
  for (auto e : edge) {
    int c, v, nv;
    tie(c, v, nv) = e;
    if (uf.is_same(v, nv))
      continue;
    uf.connect(v, nv);
    tree[v].push_back(nv);
    tree[nv].push_back(v);
  }

  // lca
  auto lca = LCA(tree, dist);
  while (q--) {
    int s, t;
    cin >> s >> t;
    s--, t--;
    cout << lca.get_min_cost(s, t) << endl;
  }
}