題目鏈接：點擊查看

題目大意：去原網址看吧

題目分析：因為是在刷克魯斯卡爾重構樹的題目，所以稍微思考一下就能想出解法了，首先如果水位線固定了，剩下的邊組成的最小生成樹也是一定的，此時同一個連通塊內的點對答案的貢獻都是相同的，因為車子可以隨便開，這樣連通塊的貢獻，就是連通塊內距離點 1 最近的點了

這樣如何找相應的連通塊呢？可以對所有邊降序排序，建立克魯斯卡爾重構樹，對于點 x 來說，找到權值大于水位線，且深度最小的祖先，這一步可以用樹上倍增來完成，此時這個祖先的子樹中的點兩兩都可以互相達到了，顯然包括了點 x ，只需要求出這些點中距離點 1 最近的點就好了

至于如何求出某個點的子樹中，距離點 1 最近的點，這個預先跑一下迪杰斯特拉，在重構樹建好后，在樹上跑一邊 dfs 就好了

相對于上一道題目來說比較簡單，好多代碼直接復用下來的（懶）：https://blog.csdn.net/qq_45458915/article/details/108187207

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=4e5+100;const int M=8e5+100;template<typename T> struct Dij {const static int N=4e5+100;const static int M=8e5+100;struct Edge{int to,next;T w;}edge[M];int head[N],cnt;//鏈式前向星 T d[N];bool vis[N];void addedge(int u,int v,T w){edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}struct Node{int to;T w;Node(int TO,T W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;}};void Dijkstra(int st){priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,0x3f,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;T w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}}}void init(){memset(head,-1,sizeof(head));cnt=0; } };Dij<int>dij;int n,m,limit,dp[N][25],f[N],ans[N],val[N];struct Edge {int u,v,w,h;bool operator<(const Edge& t)const{return h>t.h;} }edge[N];vector<int>node[N];void dfs(int u,int fa) {ans[u]=dij.d[u];dp[u][0]=fa;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(auto v:node[u]){if(v==fa)continue;dfs(v,u);ans[u]=min(ans[u],ans[v]);} } /*并查集+克魯斯卡爾重構樹*/ int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }void Ex_Kruskal() {int index=n;for(int i=1;i<=n<<1;i++)f[i]=i;sort(edge+1,edge+1+m);for(int i=1;i<=m;i++){int xx=find(edge[i].u),yy=find(edge[i].v);if(xx!=yy){f[xx]=f[yy]=++index;val[index]=edge[i].h;node[index].push_back(xx);node[index].push_back(yy);}} } /*并查集+克魯斯卡爾重構樹*/ int get_pos(int u,int up)//樹上倍增找滿足的祖先 {for(int i=20;i>=0;i--)if(dp[u][i]!=0&&val[dp[u][i]]>up)u=dp[u][i];return u; }void init(int n) {for(int i=1;i<=n<<1;i++)node[i].clear();limit=log2(n)+1;dij.init(); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d%d",&n,&m);init(n);for(int i=1;i<=m;i++){scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w,&edge[i].h);dij.addedge(edge[i].u,edge[i].v,edge[i].w);dij.addedge(edge[i].v,edge[i].u,edge[i].w);}dij.Dijkstra(1);Ex_Kruskal();dfs(find(1),0);int q,k,s,last=0;scanf("%d%d%d",&q,&k,&s);while(q--){int v,p;scanf("%d%d",&v,&p);v=(v+k*last-1)%n+1;p=(p+k*last)%(s+1);v=get_pos(v,p);printf("%d\n",last=ans[v]);}}return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 - P4768 [NOI2018]归程(Kruskal重构树+树上倍增+最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。