代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
    ll x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*f;
}
#define d rd()
#define pb push_back
const ll N=450010;
struct edge{ll v,w,nx;}e[N<<1];
ll hd[N],cnt;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
    ll ans=1;while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;b>>=1;
    }return ans;
}ll n,m,num;
ll fa[N*2];
ll find(ll x){if(fa[x]==x)return x;else return fa[x]=find(fa[x]);}
struct node{ll u,v,w;}a[N*2];
bool cmp(node a,node b){return a.w>b.w;}
ll val[N*2];
vi ee[N*2];
bool vis[N*2];
ll f[N*2][20];
ll dis[N*2];
void dfs(ll u,ll fat){vis[u]=1,f[u][0]=fat;
    fe(i,ee[u]){
        ll v=ee[u][i];if(v==fat)continue;
        dfs(v,u);dis[u]=min(dis[u],dis[v]);
    }
}
struct nodd{ll x,id;};
bool operator <(nodd a,nodd b){return a.x>b.x;}
priority_queue<nodd>q;
bool fl[N*2];
void dij(){
    f(i,1,n)fl[i]=0;dis[1]=0;
    q.push({0,1});while(!q.empty()){
        ll u=q.top().id;q.pop();
        if(fl[u])continue;fl[u]=1;
        for(int i=hd[u];i;i=e[i].nx){
            ll v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push({dis[v],v});
            }
        }
    }
}
int main(){
    wt{
        n=d,m=d;
        f(i,1,n*2){
            fa[i]=i,val[i]=0;
            ee[i].clear();hd[i]=0;
            f(j,0,19)f[i][j]=0;
            vis[i]=0;dis[i]=0x3f3f3f3f;
        }
        cnt=0;num=0;
        f(i,1,m){
            ll u=d,v=d,w=d,ww=d;
            add(u,v,w),add(v,u,w);
            a[i]={u,v,ww};
        }sort(a+1,a+m+1,cmp);num=n;
        f(i,1,m){
            ll u=find(a[i].u),v=find(a[i].v),w=a[i].w;
            if(u==v)continue;
            val[++num]=w;
            ee[num].pb(u),ee[num].pb(v);
            ee[u].pb(num),ee[v].pb(num);
            fa[u]=num,fa[v]=num;
        }dij();//f(i,1,n)cout<<dis[i]<<" ";cout<<endl;
        for(int i=num;i>=1;i--)if(!vis[i])dfs(i,0);
        f(j,1,19)f(i,1,num)f[i][j]=f[f[i][j-1]][j-1];
        ll Q=d,K=d,S=d,la=0;
        while(Q--){
            ll u=d,x=d;
            u=(u+K*la-1)%n+1;x=(x+K*la)%(S+1);ll v=u;
            // cout<<u<<" "<<x<<endl;
            for(int i=19;i>=0;i--)
                if(f[v][i]&&val[f[v][i]]>x)v=f[v][i];
            // cout<<v<<endl;
            printf("%lld\n",la=dis[v]);
        }
    }
    
    return 0;
}

评测结果