题目描述
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图（节点的编号从 1 至 n）。我们依次用 l,a 描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免 的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。
Yazid 是一名来自魔力之都的OIer，刚参加完ION2018 的他将踏上归程，回到他 温暖的家。 Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q 天，每一天Yazid 都会告诉你他的出发点 v ，以及当天的水位线p。 每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着：
车会在新的出发点被准备好。
Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。 本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。
输入
单个测试点中包含多组数据。输入的第一行为一个非负整数T，表示数据的组数。
接下来依次描述每组数据，对于每组数据：
第一行 2 个非负整数 n,m分别表示节点数、边数。
接下来 m 行，每行 4 个正整数u, v, l, a描述一条连接节点 u, v 的、长度为 l、海拔为 a 的边。 在这里，我们保证1≤u,v≤n。
接下来一行 3 个非负数 Q, K, S ，其中 Q 表示总天数，K∈0,1 是一个会在下面被用到的系数，S 表示的是可能的最高水位线。
接下来 Q 行依次描述每天的状况。每行 2 个整数 v0;p0 描述一天：
这一天的出发节点为v=v0+K×lastans−1)modn+1。
这一天的水位线为p=p0+K×lastans)modS+1)。
其中 lastans 表示上一天的答案（最小步行总路程）。特别地，我们规定第 1 天时 lastans = 0。 在这里，我们保证1≤v0≤n,0≤p0≤S 。
对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。
输出
依次输出各组数据的答案。对于每组数据：
输出 Q 行每行一个整数，依次表示每天的最小步行总路程。
样例输入
1 4 3 1 2 50 1 2 3 100 2 3 4 50 1 5 0 2 3 0 2 1 4 1 3 1 3 2
样例输出
0 50 200 50 150
题解
kruskal重构树终于有用了。先dijstra求一遍最短路，以海拔建最大生成树，然后kruskal重构树。很容易想到，我们求一遍 x 到1的边中海拔最小的h，如果h大于水位线，那么一定是可以开车回家的；如果h小于等于水位线，那么在到这条边之前就得下车走路。如何找到该下车的点？重构树上的每个点都对应在原生成树上的一段区间，且重构树的深度越小，对应的区间越大。那么找到重构树上的大于水位线的深度最小的点，答案就等于它所对应的生成树上的点距离1号点的最短路的最小值。做法：最短路+kruskal重构树+树上倍增。
#include<queue> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=800010+50; const int maxm=2*maxn; int fir[maxn],to[maxm],nex[maxm],wi[maxm],ecnt,vis[maxn]; int val[maxn],fat[maxn],d[maxn],mi[maxn],anc[maxn][23]; int T,cnt,n,m,u,v,l,aa,Q,K,S,lastans,v0,p0,vv,pp; priority_queue< pair<ll,int> > q; struct node{int x,y,z;}a[maxm]; int cmpconst node &a,const node &b){return a.z>b.z;} #define mema,b) memseta,b,sizeofa)) void init){ memfir,0);memto,0);memnex,0);memwi,0);ecnt=0;lastans=0; memval,0);memfat,0);memmi,0);mema,0);memanc,0); } void init2){ memfir,0);memto,0);memnex,0);memwi,0);ecnt=0; } void add_edgeint u,int v,int w){ nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;wi[ecnt]=w; } int fatherint x){ ifx!=fat[x]) fat[x]=fatherfat[x]); return fat[x]; } template<typename T>void readT& aa){ char cc; ll ff;aa=0;cc=getchar);ff=1; whilecc<'0'||cc>'9')&&cc!='-') cc=getchar); ifcc=='-') ff=-1,cc=getchar); whilecc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar); aa*=ff; } void dfsint u){ mi[u]=d[u]; forint e=fir[u];e;e=nex[e]){ int v=to[e]; anc[v][0]=u; dfsv); mi[u]=minmi[u],mi[v]); } } void dij){ memsetvis,0,sizeofvis)); memsetd,111,sizeofd)); d[1]=0; q.pushmake_pair0,1)); while!q.empty)){ int u=q.top).second; q.pop); ifvis[u]) continue; vis[u]=1; forint e=fir[u];e;e=nex[e]){ int v=to[e]; ifd[u]+wi[e]<d[v]){ d[v]=d[u]+wi[e]; q.pushmake_pair-d[v],v)); } } } } void kruskal){ sorta+1,a+1+m,cmp); forint i=1;i<=m;i++){ int fa=fathera[i].x),fb=fathera[i].y); iffa!=fb){ val[++cnt]=a[i].z; fat[cnt]=fat[fa]=fat[fb]=cnt; add_edgecnt,fa,0); add_edgecnt,fb,0); } } dfscnt); } int main){ readT); whileT--){ init); readn),readm);cnt=n; forint i=1;i<=n;i++) fat[i]=i; forint i=1;i<=m;i++){ readu),readv),readl),readaa); a[i].x=u;a[i].y=v;a[i].z=aa; add_edgeu,v,l); add_edgev,u,l); } dij); init2); kruskal); forint i=1;1<<i)<=cnt;i++) forint u=1;u<=cnt;u++) anc[u][i]=anc[anc[u][i-1]][i-1]; readQ),readK),readS); whileQ--){ readv0),readp0); vv=v0+K*lastans-1)%n+1; pp=p0+K*lastans)%S+1); forint i=22;i>=0;i--) ifanc[vv][i]&&val[anc[vv][i]]>pp) vv=anc[vv][i]; printf"%d ",mi[vv]);lastans=mi[vv]; } } return 0; }
最后吐槽下卡spfa的恶劣行为。。。