#line 1 "test/aoj_0575.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575"
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <map>
#include <queue>
#include <vector>
#line 1 "algorithm/parallel_binary_search.cpp"
/**
* @brief 並列二分探索
* @author えびちゃん
*/
#include <cstddef>
#line 11 "algorithm/parallel_binary_search.cpp"
template <typename StatefulPredicate, typename RandomIt>
std::vector<size_t> parallel_binary_search(
StatefulPredicate spred, RandomIt first, RandomIt last
) {
// result[i] = j if spred(first[i]) returns true for state j-1 (and
// before that) and returns false for state j (and after that).
size_t size = spred.size();
std::vector<size_t> lb(std::distance(first, last), 0);
std::vector<size_t> ub(lb.size(), size+1);
bool determined = false;
while (!determined) {
determined = true;
std::vector<std::vector<RandomIt>> ev(size+1);
auto it = first;
for (size_t i = 0; i < lb.size(); ++i) {
auto cur = it++;
if (!(ub[i] - lb[i] > 1)) continue;
size_t mid = (lb[i] + ub[i]) >> 1;
ev[mid].push_back(cur);
determined = false;
}
auto sp = spred;
for (size_t i = 0; i <= size; ++i) {
for (auto const& e: ev[i]) {
(sp(*e)? lb[e-first]: ub[e-first]) = i;
}
if (i < size) sp.next();
}
}
return ub;
}
#line 1 "DataStructure/disjoint_set.cpp"
/**
* @brief 素集合データ構造
* @author えびちゃん
*/
#line 11 "DataStructure/disjoint_set.cpp"
#include <utility>
#line 13 "DataStructure/disjoint_set.cpp"
class disjoint_set {
public:
using size_type = size_t;
private:
mutable std::vector<intmax_t> M_c;
public:
disjoint_set() = default;
explicit disjoint_set(size_type n): M_c(n, -1) {}
void reset() { M_c.assign(M_c.size(), -1); }
size_type representative(size_type v) const {
if (M_c[v] < 0) return v;
return (M_c[v] = representative(M_c[v]));
}
bool unite(size_type u, size_type v) {
u = representative(u);
v = representative(v);
if (u == v) return false;
if (-M_c[u] > -M_c[v]) std::swap(u, v);
M_c[v] += M_c[u];
M_c[u] = v;
return true;
}
bool equivalent(size_type u, size_type v) const {
return (representative(u) == representative(v));
}
size_type size() const noexcept { return M_c.size(); }
size_type count(size_type v) const {
return -M_c[representative(v)];
}
};
#line 1 "Graph/adjacency_list.cpp"
/**
* @brief 重みつきグラフの隣接リスト
* @author えびちゃん
*/
#line 11 "Graph/adjacency_list.cpp"
#include <type_traits>
#line 13 "Graph/adjacency_list.cpp"
template <typename WeightType>
class weighted_edge {
public:
using size_type = size_t;
using weight_type = WeightType;
protected:
size_type M_src, M_dst;
weight_type M_weight;
public:
weighted_edge() = default;
weighted_edge(weighted_edge const&) = default;
weighted_edge(weighted_edge&&) = default;
weighted_edge(size_type s, size_type d, weight_type w):
M_src(s), M_dst(d), M_weight(w)
{}
weighted_edge& operator =(weighted_edge const&) = default;
weighted_edge& operator =(weighted_edge&&) = default;
bool operator <(weighted_edge const& other) const {
if (M_weight < other.M_weight) return true;
if (other.M_weight < M_weight) return false;
if (M_src != other.M_src) return M_src < other.M_src;
return M_dst < other.M_dst;
}
size_type source() const { return M_src; }
size_type target() const { return M_dst; }
weight_type weight() const { return M_weight; }
};
struct directed_tag {};
struct undirected_tag {};
template <typename Edge, typename Directedness>
class adjacency_list {
public:
using size_type = size_t;
using edge_type = Edge;
using weight_type = typename Edge::weight_type;
private:
std::vector<std::vector<edge_type>> M_g;
public:
adjacency_list() = default;
adjacency_list(adjacency_list const&) = default;
adjacency_list(adjacency_list&&) = default;
explicit adjacency_list(size_type n): M_g(n) {}
template <typename... Args>
void emplace(size_type src, size_type dst, Args... args) {
M_g[src].emplace_back(src, dst, args...);
if (std::is_same<Directedness, undirected_tag>::value)
M_g[dst].emplace_back(dst, src, args...);
}
void sort_by_index() {
auto cmp = [](auto const& e1, auto const& e2) {
return e1.target() < e2.target();
};
for (auto v: M_g) std::sort(v.begin(), v.end(), cmp);
}
size_type size() const { return M_g.size(); }
auto const& operator [](size_type i) const { return M_g[i]; }
};
#line 1 "utility/limits.cpp"
/**
* @brief 型依存の定数
* @author えびちゃん
*/
#include <limits>
#line 11 "utility/limits.cpp"
template <typename Tp>
class limits: public std::numeric_limits<Tp> {};
template <typename T1, typename T2>
class limits<std::pair<T1, T2>> {
public:
static constexpr auto min() {
return std::make_pair(limits<T1>::min(), limits<T2>::min());
}
static constexpr auto max() {
return std::make_pair(limits<T1>::max(), limits<T2>::max());
}
};
#line 15 "test/aoj_0575.test.cpp"
class spred {
disjoint_set M_ds;
std::vector<std::vector<std::pair<size_t, size_t>>> M_es;
size_t M_st;
public:
spred() = default;
spred(size_t n, std::vector<std::vector<std::pair<size_t, size_t>>> const& es):
M_ds(n), M_es(es), M_st(es.size()) {}
void next() {
for (auto const& e: M_es[--M_st]) M_ds.unite(e.first, e.second);
}
bool operator ()(std::pair<size_t, size_t> const& e) {
return !M_ds.equivalent(e.first, e.second);
}
size_t size() const { return M_es.size(); }
};
template <typename Tp>
using greater_priority_queue = std::priority_queue<Tp, std::vector<Tp>, std::greater<>>;
int main() {
size_t n, m, k, q;
scanf("%zu %zu %zu %zu", &n, &m, &k, &q);
adjacency_list<weighted_edge<int>, undirected_tag> g(n);
for (size_t i = 0; i < m; ++i) {
size_t u, v;
int w;
scanf("%zu %zu %d", &u, &v, &w);
--u, --v;
g.emplace(u, v, w);
}
std::vector<size_t> f(k);
for (auto& fi: f) scanf("%zu", &fi), --fi;
std::vector<int> dist(n, limits<int>::max());
greater_priority_queue<std::pair<int, size_t>> pq;
for (auto fi: f) {
dist[fi] = 0;
pq.emplace(0, fi);
}
while (!pq.empty()) {
auto [w, v] = pq.top();
pq.pop();
if (w > dist[v]) continue;
for (auto const& e: g[v]) {
size_t nv = e.target();
int nw = dist[v] + e.weight();
if (dist[nv] > nw) {
dist[nv] = nw;
pq.emplace(nw, nv);
}
}
}
std::map<int, size_t> enc;
std::vector<int> dec;
for (auto d: dist) enc[d];
{
size_t i = 0;
for (auto& p: enc) {
p.second = i++;
dec.push_back(p.first);
}
}
std::vector<std::vector<std::pair<size_t, size_t>>> es(dec.size());
for (size_t i = 0; i < n; ++i) {
for (auto const& e: g[i]) {
size_t u = e.source();
size_t v = e.target();
if (dist[u] + e.weight() <= dist[v]) {
es[enc.at(dist[u])].emplace_back(u, v);
}
if (dist[u] <= dist[v]) {
es[enc.at(dist[u])].emplace_back(u, v);
}
}
}
std::vector<std::pair<size_t, size_t>> st(q);
for (auto& p: st) scanf("%zu %zu", &p.first, &p.second), --p.first, --p.second;
auto res = parallel_binary_search(spred(n, es), st.begin(), st.end());
for (auto ri: res) printf("%d\n", dec[es.size()-ri]);
}
test/aoj_0575.test.cpp