做最好的网站新新,招聘网站设计师要求,辽宁建设工程信息网登录入口官方,抖音代运营需要什么正题
题目链接:https://www.luogu.com.cn/problem/P4768 题目大意 nnn个点mmm条边的无向图#xff0c;然后每条边有水位和长度。
每次询问一个(v,w)(v,w)(v,w)表示从vvv点出发走高度超过www的路径到达一个点xxx使得x∼1x\sim1x∼1的最短路最短。 解题思路
先用DijDijDij跑出…正题
题目链接:https://www.luogu.com.cn/problem/P4768 题目大意
nnn个点mmm条边的无向图然后每条边有水位和长度。
每次询问一个(v,w)(v,w)(v,w)表示从vvv点出发走高度超过www的路径到达一个点xxx使得x∼1x\sim1x∼1的最短路最短。 解题思路
先用DijDijDij跑出111的单源最短路然后边权从大到小排序建立一颗KruskalKruskalKruskal重构树这样的话如果一个权值为valvalval的点的子树表示在这颗子树中走权值大于valvalval的点的话这棵子树中任意点之间可以相互到达。
所有我们每个点维护子树中最小的最短路然后对于询问点用倍增跳到满足条件的最上面的节点就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N800010;
struct edge_node{ll x,y,w;
}e[N];
struct node{ll to,next,w;
}a[N];
struct point_node{ll pos,dis;
};
bool operator(point_node x,point_node y)
{return x.disy.dis;}
priority_queuepoint_node q;
ll n,m,Q,k,s,cnt,tot,lastans,T;
ll fa[N],f[N],g[N][25],val[N],ls[N];
bool v[N];
void addl(ll x,ll y,ll w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;
}
bool cmp(edge_node x,edge_node y)
{return x.wy.w;}
void dij(){q.push((point_node){1,0});memset(v,0,sizeof(v));memset(f,127,sizeof(f));f[1]0;while(!q.empty()){ll xq.top().pos;q.pop();if(v[x]) continue;v[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y])q.push((point_node){y,f[y]});}}}return;
}
ll find(ll x)
{return (xfa[x])?x:(fa[x]find(fa[x]));}
void dfs(ll x)
{for(ll ils[x];i;ia[i].next){ll ya[i].to;g[y][0]x;dfs(y);f[x]min(f[x],f[y]);}
}
ll up(ll x,ll p){for(ll i24;i0;i--)if(val[g[x][i]]p) xg[x][i];return x;
}
void work()
{scanf(%lld%lld,n,m);for(ll i1;im;i){ll w;scanf(%lld%lld%lld%lld,e[i].x,e[i].y,w,e[i].w);addl(e[i].x,e[i].y,w);addl(e[i].y,e[i].x,w);}dij();tot0;memset(ls,0,sizeof(ls));sort(e1,e1m,cmp);for(ll i1;inm;i)fa[i]i;cntn;for(ll i1;im;i){ll fxfind(e[i].x),fyfind(e[i].y);if(fx!fy){val[cnt]e[i].w;fa[fx]cnt;fa[fy]cnt;addl(cnt,fx,0);addl(cnt,fy,0);}}dfs(find(1));for(ll i1;i25;i)for(ll j1;jcnt;j)g[j][i]g[g[j][i-1]][i-1];scanf(%lld%lld%lld,Q,k,s);lastans0;while(Q--){ll v,p;scanf(%lld%lld,v,p);v(vk*lastans-1)%n1;p(pk*lastans)%(s1);printf(%lld\n,lastansf[up(v,p)]);}
}
int main()
{scanf(%lld,T);while(T--){memset(ls,0,sizeof(ls));memset(val,0,sizeof(val));memset(g,0,sizeof(g));tot0; work();}
}
