\u514b\u9c81\u65af\u5361\u5c14\u91cd\u6784\u6811\u6a21\u677f\u9898\u3002
\n\u6211\u4eec\u53d1\u73b0\uff0c\u8fd9\u4e00\u9898\u53ef\u4ee5\u62c6\u6210\u4e24\u4e2a\u6b65\u9aa4\u3002\u7b2c\u4e00\u4e2a\u6b65\u9aa4\uff0c\u662f\u627e\u5230\u6240\u6709u\u53ef\u4ee5\u901a\u8fc7\u5171\u4eab\u5355\u8f66\u8fbe\u5230\u7684\u70b9\uff1b\u7b2c\u4e8c\u4e2a\u6b65\u9aa4\uff0c\u662f\u627e\u5230\u8fd9\u4e9b\u70b9\u4e2d\u5230\u539f\u70b9\u6700\u5c0f\u7684\u70b9\u7684\u8ddd\u79bb\u3002
\n\u6211\u4eec\u5bb9\u6613\u53d1\u73b0\uff0c\u7b2c\u4e00\u4e2a\u6b65\u9aa4\u548c\u957f\u5ea6\u65e0\u5173\uff0c\u7b2c\u4e8c\u4e2a\u6b65\u9aa4\u548c\u6d77\u62d4\u65e0\u5173\u3002
\n\u9996\u5148\u8003\u8651\u7b2c\u4e00\u4e2a\u6b65\u9aa4\u3002
\n\u6211\u4eec\u5efa\u51fa\u4e00\u68f5\u514b\u9c81\u65af\u5361\u5c14\u91cd\u6784\u6811\u2014\u2014\u514b\u9c81\u65af\u5361\u5c14\u91cd\u6784\u6811\u662f\u8fd9\u6837\u7684\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\uff1a\u5f53\u4f60\u4f7f\u7528\u514b\u9c81\u65af\u5361\u5c14\u7b97\u6cd5\u5efa\u6700\u5c0f\/\u6700\u5927\u751f\u6210\u6811\u7684\u65f6\u5019\uff0c\u6bcf\u4e00\u6b21\u5408\u5e76\uff0c\u4f60\u65b0\u5efa\u4e00\u4e2a\u8282\u70b9p\uff0c\u8fd9\u4e2a\u70b9\u7684\u70b9\u6743\u662f\u8fd9\u4e00\u6b21\u5408\u5e76\u901a\u8fc7\u7684\u8fb9\u7684\u8fb9\u6743\uff0c\u7136\u540e\u5c06\u5373\u5c06\u5408\u5e76\u7684\u4e24\u4e2a\u70b9\u7684\u6839\u8282\u70b9\u5408\u5e76\u5230p\u4e0b\u3002\u8fd9\u6837\u6211\u4eec\u6784\u9020\u51fa\u4e86\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u5176\u4e2d\u6240\u6709\u53f6\u5b50\u8282\u70b9\u662f\u539f\u56fe\u4e0a\u7684\u8282\u70b9\u3002
\n\u514b\u9c81\u65af\u5361\u5c14\u91cd\u6784\u6811\u6ee1\u8db3\u4e00\u4e9b\u6709\u610f\u4e49\u7684\u6027\u8d28\u3002
\n\u4e0d\u59a8\u4ee5\u8fd9\u9898\u4e3a\u4f8b\uff0c\u6211\u4eec\u6784\u9020\u4e00\u68f5\u6700\u5927\u751f\u6210\u6811\uff0c\u90a3\u4e48\u4e24\u70b9\u4e4b\u95f4\u7684lca\u7684\u70b9\u6743\u5c31\u662f\u8fd9\u4e24\u4e2a\u70b9\u4e4b\u95f4\u8def\u5f84\u4e2d\u8fb9\u6743\u6700\u5927\u7684\u503c\u3002\u6362\u53e5\u8bdd\u8bf4\uff0c\u4eceu\u5728d\u7684\u964d\u6c34\u4e0b\u53ef\u4ee5\u5230\u7684\u8282\u70b9\uff0c\u5c31\u662f\u6240\u6709\u548cu\u7684lca\u7684\u70b9\u6743\u5927\u4e8e\u7b49\u4e8ed\u7684\u8282\u70b9\u3002\u8003\u8651\u5230\u8fd9\u662f\u4e00\u68f5\u6700\u5927\u751f\u6210\u6811\uff0c\u6bcf\u4e2a\u70b9\u7684\u7236\u4eb2\u8282\u70b9\u7684\u70b9\u6743\u4e0d\u4f1a\u5927\u4e8e\u8fd9\u4e2a\u8282\u70b9\u3002\u8fd9\u4e5f\u5c31\u610f\u5473\u7740\uff0c\u6211\u4eec\u9700\u8981\u627e\u5230u\u7684\u6700\u9ad8\u7684\u7956\u5148\uff0c\u4f7f\u5f97\u8fd9\u4e2a\u7956\u5148\u7684\u70b9\u6743\u5927\u4e8e\u7b49\u4e8ed\u3002\u4e0d\u59a8\u79f0\u8fd9\u4e2a\u7956\u5148\u4e3aw\uff0c\u90a3\u4e48w\u7684\u5b50\u6811\u7684\u6240\u6709\u53f6\u5b50\u8282\u70b9\uff0c\u5c31\u662fu\u5728d\u7684\u964d\u6c34\u4e0b\u80fd\u62b5\u8fbe\u7684\u8282\u70b9\u3002
\n\u4e8e\u662f\uff0c\u6211\u4eec\u6c42\u51fa\u4e86\u7b2c\u4e00\u4e2a\u6b65\u9aa4\u7684\u89e3\u3002
\n\u7136\u540e\u6211\u4eec\u8003\u8651\u7b2c\u4e8c\u4e2a\u6b65\u9aa4\u7684\u89e3\u3002\u8003\u8651\u5230\u8fd9\u662f\u4e00\u5f20\u65e0\u5411\u56fe\uff0c\u6211\u4eec\u5148\u6c42\u51fa1\u53f7\u8282\u70b9\u5230\u6240\u6709\u8282\u70b9\u7684\u8ddd\u79bb\uff0c\u7136\u540e\u628a\u8fd9\u4e9b\u503c\u8d4b\u5230\u53f6\u5b50\u8282\u70b9\u4e0a\uff0c\u4e0d\u59a8\u79f0\u5b83\u4e3a\u300e\u8ddd\u79bb\u6743\u503c\u300f\u3002\u56e0\u4e3a\u6211\u4eec\u6bcf\u4e00\u6b21\u6c42min\u5fc5\u7136\u662f\u6c42\u300c\u67d0\u4e2a\u70b9\u7684\u5b50\u6811\u4e2d\u6240\u6709\u53f6\u5b50\u8282\u70b9\u7684\u300e\u8ddd\u79bb\u6743\u503c\u300f\u7684\u6700\u5c0f\u503c\u300d\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u8fdb\u884c\u6811\u5f62dp\uff0c\u628a\u8fd9\u4e2a\u6700\u5c0f\u503c\u7684\u4fe1\u606f\u76f4\u63a5\u8bb0\u5f55\u5230\u6bcf\u4e2a\u865a\u62df\u8282\u70b9\u4e0a\u3002
\n\u8fd9\u5c31\u505a\u5b8c\u4e86\u3002<\/p>\n\n\n\n
<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\nconst int N=800005,M=800005;\nconst int INF=0x3f3f3f3f;\n\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\n\nstruct ee{\n\tint v;\n\tint w;\n\tint a;\n\tint nxt;\n}e[M<<1];\nint h[N],et=0;\ninline void Eadd(int U,int V,int W,int A){\n\te[++et]=(ee){V,W,A,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V,int W,int A){\n\tEadd(U,V,W,A);\n\tEadd(V,U,W,A);\n}\nstruct tee{\n\tint v;\n\tint nxt;\n}te[N<<1];\nint g[N],tet=0;\ninline void tEadd(int U,int V){\n\tte[++et]=(tee){V,g[U]};\n\tg[U]=et;\n}\ninline void tadd(int U,int V){\n\ttEadd(U,V);\n\ttEadd(V,U);\n}\nstruct data{\n\tint u;int v;int a;\n}lst[M];\ninline bool cmp(const data &A,const data &B){\n\treturn A.a>B.a;\n}\nint ff[N],f[N][20];\ninline int fa(int X){\n\treturn ff[X]==X?ff[X]:ff[X]=fa(ff[X]);\n}\nint val[N];\nint n,m,cnt,rt;\ninline void uni(int X,int Y){\n\tX=fa(X),Y=fa(Y);\n\ttadd(ff[X],cnt);tadd(ff[Y],cnt);\n\tff[X]=ff[Y]=cnt;\n}\ninline void kruskal(){\n\tcnt=n;\n\tfor(int i=1;i<=m;++i){\n\t\tif(fa(lst[i].u)==fa(lst[i].v)){\n\t\t\tcontinue;\n\t\t}\n\t\tval[++cnt]=lst[i].a;\n\t\tuni(lst[i].u,lst[i].v);\n\t\tif(cnt==n*2-1){\n\t\t\tbreak;\n\t\t}\n\t}\n\trt=fa(1);\n}\nint dis[N],vis[N];\nstruct cmp2{\n\tinline bool operator()(int A,int B){\n\t\treturn dis[A]>dis[B];\n\t}\n};\npriority_queue< int,vector<int>,cmp2 > q;\ninline void dij(){\n\tfor(int i=2;i<=n*2;++i){\n\t\tdis[i]=INF;vis[i]=0;\n\t}\n\tvis[1]=1,dis[1]=0;\n\tq.push(1);\n\tint p;\n\twhile(!q.empty()){\n\t\tp=q.top();q.pop();vis[p]=0; \n\t\tfor(int i=h[p];i;i=e[i].nxt){\n\t\t\tif(dis[e[i].v]>dis[p]+e[i].w){\n\t\t\t\tdis[e[i].v]=dis[p]+e[i].w;\n\t\t\t\tif(!vis[e[i].v]){\n\t\t\t\t\tq.push(e[i].v);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n}\ninline void dfs0(int X){\n\tfor(int i=g[X];i;i=te[i].nxt){\n\t\tif(te[i].v==f[X][0]){\n\t\t\tcontinue;\n\t\t}\n\/\/\t\tprintf(\"%d %d\\n\",X,te[i].v);\n\t\tf[te[i].v][0]=X;\n\t\tfor(int j=1;j<=18;++j){\n\t\t\tf[te[i].v][j]=f[f[te[i].v][j-1]][j-1];\n\t\t}\n\t\tdfs0(te[i].v);\n\t\tdis[X]=Min(dis[X],dis[te[i].v]);\n\t}\n}\ninline int qry(int X,int D){\n\tfor(int i=18;i>=0;--i){\n\t\tif(val[f[X][i]]>D){\n\t\t\tX=f[X][i];\n\t\t}\n\t}\n\treturn dis[X];\n}\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tet=tet=0;\n\tfor(int i=1;i<=n*2;++i){\n\t\tg[i]=h[i]=0;\n\t}\n\tint u,v,w,a;\n\tfor(int i=1;i<=m;++i){\n\t\tscanf(\"%d%d%d%d\",&u,&v,&w,&a);\n\t\tadd(u,v,w,a);\n\t\tlst[i]=(data){u,v,a};\n\t}\n\tstd::sort(lst+1,lst+1+m,cmp);\n\tfor(int i=1;i<=n*2;++i){\n\t\tff[i]=i;val[i]=INF;\n\t}\n\tkruskal();\n\tdij();\n\tdfs0(rt);\n\/\/\tfor(int i=1;i<=rt;++i){\n\/\/\t\tprintf(\"%d \",dis[i]);\n\/\/\t}\n\/\/\tputs(\"\");\n\tint Q,K,S,lans=0,x,d;\n\tscanf(\"%d%d%d\",&Q,&K,&S);\n\tfor(int i=1;i<=Q;++i){\n\t\tscanf(\"%d%d\",&x,&d);\n\t\tx=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);\n\t\tprintf(\"%d\\n\",lans=qry(x,d));\n\t}\n}\nint main(){\n\tint T;\n\tscanf(\"%d\",&T);\n\twhile(T--){\n\t\tinit();\n\t}\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u514b\u9c81\u65af\u5361\u5c14\u91cd\u6784\u6811\u6a21\u677f\u9898\u3002 \u6211\u4eec\u53d1\u73b0\uff0c\u8fd9\u4e00\u9898\u53ef\u4ee5\u62c6\u6210\u4e24\u4e2a\u6b65\u9aa4\u3002\u7b2c\u4e00\u4e2a\u6b65\u9aa4\uff0c\u662f\u627e\u5230\u6240\u6709u\u53ef\u4ee5\u901a\u8fc7\u5171\u4eab\u5355\u8f66\u8fbe\u5230\u7684\u70b9\uff1b … <\/p>\n