题意
给定一个图，走过一条边的花费为权值，其中有 \(k\) 个充电点。
你需要确定一个电量的上限，使得满足从 \(a\) 走到 \(b\)。
Sol
先对于每个点求出她走到充电点最近的距离，用 \(dij\) 随便跑跑。
考虑从 \(a \to b\) 一条边的贡献。设当前的电量上限为 \(c\)。
可得：
\[c - dis_a \ge len + dis_b
\]
\[c \ge len + dis_a + dis_b
\]
求出了一条边的对答案的贡献，答案不就是 \(a \to b\) 中每条边的最大值。
直接跑最小生成树，然后上树剖跑跑就行了。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <queue>
#include <tuple>
#include <vector>
#include <bitset>
#define int long long
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e5 + 5, M = 6e5 + 5, inf = 2e18;
namespace G {
array <int, N> fir;
array <int, M> nex, to, len;
int cnt;
void add(int x, int y, int z) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
len[cnt] = z;
fir[x] = cnt;
}
}
namespace T {
array <int, N> fir;
array <int, M> nex, to, len;
int cnt;
void add(int x, int y, int z) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
len[cnt] = z;
fir[x] = cnt;
}
}
namespace Dij {
priority_queue <pii, vector <pii>, greater <pii> > q;
array <int, N> dis;
bitset <N> vis;
void dijkstra(vector <int> st) {
dis.fill(inf);
for (auto x : st) q.push(make_pair(dis[x] = 0, x));
while (!q.empty()) {
int u = q.top().se;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = G::fir[u]; i; i = G::nex[i]) {
if (dis[G::to[i]] <= dis[u] + G::len[i]) continue;
dis[G::to[i]] = dis[u] + G::len[i];
q.push(make_pair(dis[G::to[i]], G::to[i]));
}
}
}
}
namespace Hpt {
using T::fir; using T::nex; using T::to; using T::len;
array <int, N> siz, dep, fa, son;
array <int, N> cur;
void dfs1(int x) {
siz[x] = 1;
for (int i = fir[x]; i; i = nex[i]) {
if (to[i] == fa[x]) continue;
fa[to[i]] = x;
dep[to[i]] = dep[x] + 1;
dfs1(to[i]);
siz[x] += siz[to[i]];
cur[to[i]] = len[i];
if (siz[to[i]] > siz[son[x]]) son[x] = to[i];
}
}
array <int, N> dfn, idx, top;
int cnt;
void dfs2(int x, int Mgn) {
cnt++;
dfn[x] = cnt;
idx[cnt] = x;
top[x] = Mgn;
if (son[x]) dfs2(son[x], Mgn);
for (int i = fir[x]; i; i = nex[i]) {
if (to[i] == fa[x] || to[i] == son[x]) continue;
dfs2(to[i], to[i]);
}
}
}
array <int, N> s;
namespace Uni {
array <int, N> fa, siz;
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x),
fy = find(y);
if (siz[fx] > siz[fy]) swap(fx, fy);
siz[fy] += siz[fx];
fa[fx] = fy;
}
void init(int n) {
for (int i = 1; i <= n; i++)
siz[fa[i] = i] = 1;
}
}
namespace Kruskal {
#define tupl tuple <int, int, int>
array <tupl, M> edge;
void solve(int n, int m) {
sort(edge.begin() + 1, edge.begin() + 1 + m, [](tupl x, tupl y) {
return get <2>(x) < get <2>(y);
} );
Uni::init(n);
for (int i = 1; i <= m; i++) {
int u, v, w; tie(u, v, w) = edge[i];
if (Uni::find(u) == Uni::find(v)) continue;
Uni::merge(u, v); T::add(u, v, w), T::add(v, u, w);
}
}
}
namespace Sgt {
array <int, 4 * N> edge;
void pushup(int x) {
edge[x] = max(edge[x * 2], edge[x * 2 + 1]);
}
void build(int x, int l, int r) {
if (l == r) {
edge[x] = Hpt::cur[Hpt::idx[l]];
return;
}
int mid = (l + r) >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
pushup(x);
}
int query(int x, int l, int r, int L, int R) {
if (L > r || R < l) return 0;
if (L <= l && R >= r) return edge[x];
int mid = (l + r) >> 1, ans = 0;
if (L <= mid) ans = max(query(x * 2, l, mid, L, R), ans);
if (R > mid) ans = max(query(x * 2 + 1, mid + 1, r, L, R), ans);
return ans;
}
}
namespace Hpt {
int query(int x, int y, int n) {
int ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ans = max(Sgt::query(1, 1, n, dfn[top[x]], dfn[x]), ans);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ans = max(Sgt::query(1, 1, n, dfn[x] + 1, dfn[y]), ans);
return ans;
}
}
signed main() {
int n = read(), m = read(), k = read(), q = read();
for (int i = 1; i <= m; i++) {
int x = read(), y = read(), z = read();
G::add(x, y, z), G::add(y, x, z);
Kruskal::edge[i] = make_tuple(x, y, z);
}
vector <int> isl;
for (int i = 1; i <= k; i++) isl.push_back(i);
Dij::dijkstra(isl);
for (int i = 1; i <= m; i++) {
int u, v, w; tie(u, v, w) = Kruskal::edge[i];
w += Dij::dis[u] + Dij::dis[v];
Kruskal::edge[i] = make_tuple(u, v, w);
}
Kruskal::solve(n, m);
Hpt::dfs1(1), Hpt::dfs2(1, 0);
Sgt::build(1, 1, n);
// puts("@");
while (q--) {
int x = read(), y = read();
write(Hpt::query(x, y, n)), puts("");
}
return 0;
}