php实现网站消息推送,网络营销与直播专业学什么,佛山网站建设运营,淘宝指数查询入口F. Cheap Robot
给定一个无向连通图#xff0c;每条边有边权#xff0c;路过需要消耗对应的电量#xff08;边权#xff09;#xff0c;有kkk个中心点#xff0c;
问从a−ba- ba−b#xff0c;我们最少需要带多少电#xff0c;设最小为CCC#xff0c;当…F. Cheap Robot
给定一个无向连通图每条边有边权路过需要消耗对应的电量边权有kkk个中心点
问从a−ba- ba−b我们最少需要带多少电设最小为CCC当通过一条边时我们的电会减少当电不够时即不能通过当经过中心点时我们的电会立刻变为CCC
比较简单的想法处理出任意两个中心点对的最短路出来最后我们只需要得到中心点对的升序kruskalkruskalkruskal最小生成树然后每次查询两点之间的lcalcalca的权值即可。
我们假设dis[x]dis[x]dis[x]为从xxx到达最近的中心点所需要的电量
设我们以TTT电量到达了uuu点那么我们要能够到达终点注意终点是一个中心点那么一定有T≥dis[u]T \geq dis[u]T≥dis[u]
也就是说如果离uuu最近的中心点不是终点那么我们在uuu点的能量可以更新为C−dis[u]C - dis[u]C−dis[u]且有C−dis[u]≥TC - dis[u] \geq TC−dis[u]≥T
如果与uuu直接相连的边为vvv要能够到达vvv那么一定有C−dis[u]≥Wu,vC - dis[u] \geq W_{u, v}C−dis[u]≥Wu,vWu,vW_{u, v}Wu,v是边权
同时要使能从vvv到达终点那么C−dis[u]−Wu,v≥dis[v]C - dis[u] - W_{u, v} \geq dis[v]C−dis[u]−Wu,v≥dis[v]也同样成立也就是有C≥dis[u]dis[v]wu,vC \geq dis[u] dis[v] w_{u, v}C≥dis[u]dis[v]wu,v
满足上面的式子我们才可能通过一条边然后从某条边走向终点
所以我们可以把原本的一条边的边权转化为Wu,vWu,vdis[u]dis[v]W_{u, v} W_{u, v} dis[u] dis[v]Wu,vWu,vdis[u]dis[v]跑一个升序kruskalkruskalkruskal最小生成树找lcalcalca权值即可
#include bits/stdc.husing namespace std;typedef long long ll;const int N 1e6 10;int n, nn, k, m, q, ff[N];ll value[N], dis[N];int head[N], vis[N], nex[N], to[N], cnt 1;int fa[N], dep[N], sz[N], top[N], son[N], id[N], tot;struct Res {int u, v;ll w;void read() {scanf(%d %d %lld, u, v, w);}bool operator (const Res t) const {return w t.w;}
}edge[N];struct Node {int u;ll w;bool operator (const Node t) const {return w t.w;}
};vectorNode G[N];bool cmp(int x, int y) {return id[x] id[y];
}int find(int rt) {return ff[rt] rt ? rt : ff[rt] find(ff[rt]);
}void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs1(int rt, int f) {fa[rt] f, dep[rt] dep[f] 1, sz[rt] 1, id[rt] tot;for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}dfs1(to[i], rt);sz[rt] sz[to[i]];if (sz[son[rt]] sz[to[i]]) {son[rt] to[i];}}
}void dfs2(int rt, int tp) {top[rt] tp;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i head[rt]; i; i nex[i]) {if (to[i] fa[rt] || to[i] son[rt]) {continue;}dfs2(to[i], to[i]);}
}int lca(int x, int y) {while (top[x] ! top[y]) {if (dep[top[x]] dep[top[y]]) {swap(x, y);}x fa[top[x]];}return dep[x] dep[y] ? x : y;
}void kruskal() {sort(edge 1, edge 1 m);for (int i 1; i N; i) {ff[i] i;}for (int i 1, cur 1; i m cur n; i) {int u find(edge[i].u), v find(edge[i].v);if (u ^ v) {cur, nn;ff[u] ff[v] nn;value[nn] edge[i].w;add(nn, u), add(nn, v);}}dfs1(nn, 0), dfs2(nn, nn);
}void Dijkstra() {priority_queueNode q;memset(vis, 0, sizeof vis);memset(dis, 0x3f, sizeof dis);for (int i 1; i k; i) {q.push({i, 0});dis[i] 0;}while (q.size()) {int u q.top().u;q.pop();if (vis[u]) {continue;}vis[u] 1;for (auto to : G[u]) {if (dis[to.u] dis[u] to.w) {dis[to.u] dis[u] to.w;q.push({to.u, dis[to.u]});}}}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d %d %d, n, m, k, q);nn n;for (int i 1; i m; i) {edge[i].read();G[edge[i].v].push_back({edge[i].u, edge[i].w});G[edge[i].u].push_back({edge[i].v, edge[i].w});}Dijkstra();for (int i 1; i m; i) {edge[i].w dis[edge[i].u] dis[edge[i].v];}kruskal();while (q--) {int u, v;scanf(%d %d, u, v);printf(%lld\n, value[lca(u, v)]);}return 0;
}
