CF1253F Cheap Robot

Codeforces，luogu。

如果我们从走的路径长短出发去思考问题会很困难。因为目的是走到终点，求出容量，这一过程中只有行与不行之分。从此出发，对于当前点 \(u\)，可以通过走到最近的一个充电站再走回来以增加当前电量。因此我们要处理每个点到最近充电站的距离。距离可以通过建一个超级源点连向 \(k\) 个充电站，再 dijkstra 跑最短路处理。

那么由于我们要求的是 \(C\) 的最小值，我们应当在其中找到一些约束去确定其最值。

设当前电量为 \(x\)。

当前点 \(u\) 有：\(dis_u \le x \le c-dis_u\)，因为如果最近的那个充电站是终点，要能够到达；如果不是，那么要能到达，否则就没有到达终点的能力。

考虑具体化 \(x\)，\(u\) 走到的下一个点 \(v\)，当前电量为 \(c-dis_u-w(u,v)\)。

对于 \(v\) 我们可以得到： \(dis_v \le c-dis_u-w(u,v) \le c-dis_v\)。

所以我们就有：\(dis_u+w(u,v)+dis_v \le c\)，因此 \(c\) 的下限就是 \(a\) 到 \(b\) 路径上最大的 \(dis_u+w(u,v)+dis_v\) 值。因此我们将 \(dis_u+w(u,v)+dis_v \le c\) 作为边权，建成最小生成树或 kruskal 重构树，跑 \(LCA\) 即可。

我是建最小生成树并倍增维护路径上的最大权值。

CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,q;
struct Graph{
	int head[100010],etot = 1;
	struct node{ int nxt,v; ll w; }edge[800010];
	inline void add(int x,int y,ll w){
		edge[++etot] = {head[x],y,w};
		head[x] = etot;
	}
	node & operator [](const int i){ return edge[i]; }
}G,T;

struct P{
	int v;
	ll dis;
	bool friend operator <(P a,P b){ return a.dis > b.dis; }
};
ll dis[100010];
bool vis[100010];
void dij(){
	memset(dis,0x3f,sizeof dis);
	priority_queue<P> q;
	q.push({0,dis[0] = 0});
	while(!q.empty()){
		int x = q.top().v; q.pop();
		if(vis[x])continue;
		vis[x] = 1;
		for(int i = G.head[x],v = G[i].v;i;i = G[i].nxt,v = G[i].v){
			if(dis[v] > dis[x] + G[i].w){
				dis[v] = dis[x] + G[i].w;
				q.push({v,dis[v]});
			}
		}
	}
}
struct Edge{
	int u,v; ll w,cap;
	bool friend operator <(Edge a,Edge b){ return a.cap < b.cap; }
}e[300010];
struct DSU{
	int fa[100010];
	void init(int n){ for(int i = 1;i<=n;++i)fa[i] = i; }
	int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
}dsu;


int st[100010][18];
ll f[100010][18];
int dep[100010];
void dfs(int u,int fa){
	dep[u] = dep[fa] + 1;
	st[u][0] = fa;
	for(int i = 1;i<=17;++i)
		st[u][i] = st[st[u][i-1]][i-1],
		f[u][i] = max(f[u][i-1],f[st[u][i-1]][i-1]);
	for(int i = T.head[u],v = T[i].v;i;i = T[i].nxt,v = T[i].v)if(v ^ fa){
		f[v][0] = T[i].w;
		dfs(v,u);
	}
}

ll LCA(int x,int y){
	if(dep[y] < dep[x])swap(x,y);
	int t = dep[y] - dep[x];
	ll res = 0;
	for(int i = 17;~i;--i)if(t&(1<<i))res = max(res,f[y][i]),y = st[y][i];
	if(x == y)return res;
	for(int i = 17;~i;--i)if(st[x][i] ^ st[y][i]){
		res = max({res,f[x][i],f[y][i]});
		x = st[x][i], y = st[y][i];
	}
	return max({res,f[x][0],f[y][0]});
}
int main(){
	scanf("%d%d%d%d",&n,&m,&k,&q);
	for(int i = 1;i<=m;++i)
		scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w),G.add(e[i].u,e[i].v,e[i].w),G.add(e[i].v,e[i].u,e[i].w);
	for(int i = 1;i<=k;++i)G.add(0,i,0);
	dij();
	for(int i = 1;i<=m;++i)
		e[i].cap = e[i].w + dis[e[i].u] + dis[e[i].v];
	sort(e+1,e+m+1);
	dsu.init(n);
	for(int i = 1;i<=m;++i){
		int u = e[i].u, v = e[i].v; ll w = e[i].cap;
		if(dsu.find(u) == dsu.find(v))continue;
		dsu.fa[dsu.find(u)] = dsu.find(v);
		T.add(u,v,w), T.add(v,u,w);
	}
	dfs(1,0);
	int x,y;
	while(q--){
		scanf("%d%d",&x,&y);
		printf("%lld\n",LCA(x,y));
	}
	return 0;
}