归程题解

归程题解

不知道我是看错了还是咋的，

步行可以走没有积水的边，

这样接下来他就可以步行经过有积水的边

我看到这一句话，总以为只能走有积水的边，
又屈辱看题解
咳咳，使步行总长最小，我们可以考虑预处理出每个点到1的最短路，
看看车子通过没积水的边能到哪些点，输出最小值，
这怎么搞？
来一波Kruskal重构树，
没学过的可以看我的这篇博客
已知，能走到最上面的点，它的子树就都能走到
我们可以搜索出子树内最小的最短路，然后倍增，看最多能走到哪个点，输出。
代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=2e5+6,M=4e5+6;
int n,m,t,Q,K,S,cnt=0,num=0,tot=0;
int cnt2=0,head2[N<<1],fa[N<<1],head[N],tt;
int f[N<<1][21],g[N<<1][21];
ll dis[N<<1],mind[N<<1],t1,t2,ans=0;
struct edge{int nxt,to,w;}e[M<<1],gg[M<<1];
struct xd{
   int i; ll z;
   bool operator < (const xd &a) const {return z>a.z;}
}tmp,nw;
struct que{int x,y,z;}qu[M];
priority_queue<xd> q;
inline void add(int u,int v,int w){e[++cnt].nxt=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt;}
inline void add2(int u,int v,int w){gg[++cnt2].nxt=head2[u],gg[cnt2].to=v,gg[cnt2].w=w,head2[u]=cnt2;}
void dijkstra(){
    memset(dis,0x3f,sizeof(dis)),tmp.i=1,tmp.z=0,dis[1]=0,q.push(tmp);
    while(!q.empty()){
        tmp=q.top(),q.pop(); //cout<<tmp.i<<" "<<tmp.z<<endl;
        if(dis[tmp.i]<tmp.z) continue;
        for(int i=head[tmp.i];i;i=e[i].nxt){
            nw.i=e[i].to,nw.z=tmp.z+e[i].w;
            if(dis[nw.i]>nw.z) dis[nw.i]=nw.z,q.push(nw);
        }
    }
    //for(int i=1;i<=n;++i) printf("%d %lld\n",i,dis[i]);
}
inline int read(){
    int T=0,F=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
    return F*T;
}
bool cmp(que u,que v){return u.z>v.z;}
int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
bool merge(int x,int y,int z){
     x=getf(x),y=getf(y);
     if(x==y) return false;
     ++tot,f[x][0]=tot,f[y][0]=tot,g[x][0]=z,g[y][0]=z,fa[x]=fa[y]=fa[tot]=tot,add2(tot,x,z),add2(tot,y,z);
     return true;   
}
void dfs(int x){
    mind[x]=dis[x];
    for(int i=1;i<=20;++i) f[x][i]=f[f[x][i-1]][i-1],g[x][i]=min(g[x][i-1],g[f[x][i-1]][i-1]); 
    for(int i=head2[x];i;i=gg[i].nxt) dfs(gg[i].to),mind[x]=min(mind[x],mind[gg[i].to]);  
}
int main(){
    tt=read();
    while(tt--){
       n=read(),m=read(),cnt=0,cnt2=0,num=0,ans=0,tot=n,memset(dis,0x3f,sizeof(dis)),memset(head,0,sizeof(head)),memset(head2,0,sizeof(head2)),memset(g,0,sizeof(g)),memset(f,0,sizeof(f));
        for(int i=1;i<=n;++i) fa[i]=i;
       for(int i=1;i<=m;++i) qu[i].x=read(),qu[i].y=read(),t=read(),qu[i].z=read(),add(qu[i].x,qu[i].y,t),add(qu[i].y,qu[i].x,t);
       sort(qu+1,qu+m+1,cmp),dijkstra();
       for(int i=1;i<n;++i){
           ++num;
           if(num>m) break;
           if(!merge(qu[num].x,qu[num].y,qu[num].z)) --i;
    } 
        dfs(tot),Q=read(),K=read(),S=read()+1;
    for(int i=1;i<=Q;++i){
           t1=read(),t2=read(),t1=(t1+ans*K-1)%n+1,t2=(t2+ans*K)%S;
           for(int j=20;j>=0;--j) if(f[t1][j]&&t2<g[t1][j]) t1=f[t1][j];
           ans=mind[t1],printf("%lld\n",ans);
       }  
    }   
    return 0;
}

归程题解

原文：https://www.cnblogs.com/ljk123-de-bo-ke/p/11715764.html