代码

#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define int long long
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
struct Graph
{
    struct sss
    {
        int q,w,e,r,nxt;
        friend bool operator<(const sss&a,const sss&s){return a.r>s.r;}
    }a[1000005];
    int cnt,head[1000005];
    void adde(int q,int w,int e,int r)
    {
        a[++cnt].q=q;
        a[cnt].w=w;
        a[cnt].e=e;
        a[cnt].r=r;
        a[cnt].nxt=head[q];
        head[q]=cnt;
    }
    void clear(){memset(head,0,sizeof(head));cnt=0;}
}G1;
int dis[1000005],vis[1000005],cnt,n,fa[1000005],K,ans;
priority_queue<pii,vector<pii>,greater<pii>>q;
void dijstra()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(mp(0,1));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=G1.head[x];i;i=G1.a[i].nxt)
        {
            if(dis[G1.a[i].w]>dis[x]+G1.a[i].e)
            {
                dis[G1.a[i].w]=dis[x]+G1.a[i].e;
                q.push(mp(dis[G1.a[i].w],G1.a[i].w));
            }
        }
    }
}
int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
struct kruskal:public Graph
{
    int root,f[1000005],num=n,g[1000005],p[1000005][25];
    void dfs(int x,int fa)
    {
        g[x]=dis[x];
        p[x][0]=fa;
        for(int i=1;i<25;i++)p[x][i]=p[p[x][i-1]][i-1];
        for(int i=head[x];i;i=a[i].nxt)
        {
            if(a[i].w!=fa)
            {
                dfs(a[i].w,x);
                g[x]=min(g[x],g[a[i].w]);
            }
        }
    }
    void init()
    {
        num=n;
        dijstra();
        sort(G1.a+1,G1.a+G1.cnt+1);
        for(int i=1;i<=2*n;i++)fa[i]=i;
        for(int i=1;i<=n;i++)f[i]=1e18;
        for(int i=1;i<=G1.cnt;i++)
        {
            int fx=fnd(G1.a[i].q);
            int fy=fnd(G1.a[i].w);
            if(fx!=fy)
            {
                ++num;
                adde(fx,num,0,0);
                adde(num,fx,0,0);
                adde(fy,num,0,0);
                adde(num,fy,0,0);
                fa[fx]=fa[fy]=num;
                f[num]=G1.a[i].r;
            }
        }
        root=num;
        dfs(root,0);
    }
    int ask(int x,int v)
    {
        for(int i=24;~i;i--)if(f[p[x][i]]>v)x=p[x][i];
        return g[x];
    }
}T1;
int T,m,Q,S;
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        ans=0;
        G1.clear();
        T1.clear();
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int q,w,e,r;
            scanf("%lld%lld%lld%lld",&q,&w,&e,&r);
            G1.adde(q,w,e,r);
            G1.adde(w,q,e,r);
        }
        T1.init();
        scanf("%lld%lld%lld",&Q,&K,&S);
        while(Q--)
        {
            int x,y;
            scanf("%lld%lld",&x,&y);
            x=(x+K*ans-1)%n+1;
            y=(y+K*ans)%(S+1);
            printf("%lld\n",ans=T1.ask(x,y));
        }
    }
}
/*
1
5 4
1 2 3 3
4 5 5 4
1 3 4 3
2 4 2 4
1 0 5
2 3
*/

评测结果