解题：NOI 2018 归程

清新友好的题目

跑一个最短路，然后对海拔建Kruskal重构树，从最后接上去的边(最低的一个)开始DFS一下处理子树里路程的最小值。

询问是每次在重构树上倍增找到深度最浅的海拔高于当天水位线的节点，其子树内的点必定可以通过乘车互相到达。

  1 #include<queue>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int N=600005,M=1200005,X=21,inf=2e9;
  7 struct a
  8 {
  9     int x,y,s;
 10 }mst[N];
 11 struct b{int node,dist;};
 12 bool operator < (b x,b y)
 13 {
 14     return x.dist>y.dist;
 15 }
 16 priority_queue<b> hp; 
 17 int p[N],noww[M],goal[M],val[M];
 18 int P[N],Noww[M],Goal[M],mul[N][X];
 19 int vis[N],dis[N],aset[N],elev[N],mind[N];
 20 int n,m,T,Q,S,K,t1,t2,t3,t4,cnt,Cnt,tot,ans;
 21 bool cmp(a x,a y)
 22 {
 23     return x.s>y.s;
 24 }
 25 int Finda(int x)
 26 {
 27     return x==aset[x]?x:aset[x]=Finda(aset[x]);
 28 }
 29 void Link(int f,int t,int v)
 30 {
 31     noww[++cnt]=p[f],p[f]=cnt;
 32     goal[cnt]=t,val[cnt]=v;
 33     noww[++cnt]=p[t],p[t]=cnt;
 34     goal[cnt]=f,val[cnt]=v;
 35 }
 36 void Linka(int f,int t)
 37 {
 38     Noww[++Cnt]=P[f];
 39     Goal[Cnt]=t,P[f]=Cnt;
 40     Noww[++Cnt]=P[t];
 41     Goal[Cnt]=f,P[t]=Cnt;
 42 }
 43 void Init()
 44 {
 45     memset(p,0,sizeof p);
 46     memset(P,0,sizeof P);
 47     memset(mul,0,sizeof mul);
 48     memset(vis,0,sizeof vis);
 49     memset(dis,0x3f,sizeof dis);
 50     for(int i=1;i<=n;i++) aset[i]=i;
 51     cnt=Cnt=ans=0,tot=n,dis[1]=0,hp.push((b){1,0});
 52 }
 53 void Dijkstra()
 54 {
 55     while(!hp.empty())
 56     {
 57         b tt=hp.top(); hp.pop(); int tn=tt.node; 
 58         if(vis[tn]) continue; vis[tn]=true;
 59         for(int i=p[tn];i;i=noww[i])
 60             if(dis[goal[i]]>dis[tn]+val[i])
 61             {
 62                 dis[goal[i]]=dis[tn]+val[i];
 63                 hp.push((b){goal[i],dis[goal[i]]});
 64             }
 65     }
 66 }
 67 void DFS(int nde,int fth)
 68 {
 69     mul[nde][0]=fth;
 70     for(int i=1;mul[nde][i-1];i++)
 71         mul[nde][i]=mul[mul[nde][i-1]][i-1];
 72     mind[nde]=(nde<=n)?dis[nde]:inf;
 73     for(int i=P[nde];i;i=Noww[i])
 74         if(Goal[i]!=fth)
 75         {
 76             DFS(Goal[i],nde);
 77             if(mind[Goal[i]]<mind[nde])
 78                 mind[nde]=mind[Goal[i]];
 79         }
 80 }
 81 int main()
 82 {
 83     scanf("%d",&T);
 84     while(T--)
 85     {
 86         scanf("%d%d",&n,&m),Init();
 87         for(int i=1;i<=m;i++)
 88         {
 89             scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
 90             mst[i]=(a){t1,t2,t4},Link(t1,t2,t3);
 91         }
 92         Dijkstra(),sort(mst+1,mst+1+m,cmp);
 93         for(int i=1;i<=m;i++)
 94         {
 95             int tx=Finda(mst[i].x),ty=Finda(mst[i].y),ts=mst[i].s;
 96             if(tx!=ty)
 97             {
 98                 elev[++tot]=ts,aset[tot]=aset[tx]=aset[ty]=tot;
 99                 Linka(tx,tot),Linka(ty,tot);
100             }
101         }
102         DFS(tot,0),scanf("%d%d%d",&Q,&K,&S);
103         while(Q--)
104         {
105             scanf("%d%d",&t1,&t2);
106             t1=(t1+K*ans-1)%n+1,t2=(t2+K*ans)%(S+1);
107             for(int i=20;~i;i--)        
108                 if(elev[mul[t1][i]]>t2) t1=mul[t1][i];
109             printf("%d
",ans=mind[t1]);
110         }
111     }
112     return 0;
113 }

View Code