```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <algorithm>
#define ll long long
using namespace std;
const int N=5e5+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,rt;
ll dis[N],w[N<<1],dsr[N<<1];
struct node {
int u,v,l,a;
bool operator < (const node &b) const {
return a>b.a;
}
} edge[N];
struct noi_2018_t1 {
int v,nxt;
} e[N<<1];
int head[N<<1],add_tot;
void add(int u,int v) {
// cout<<u<<" "<<v<<"\n";
e[++add_tot].v=v;
e[add_tot].nxt=head[u];
head[u]=add_tot;
}
namespace bcj {
int fa[N<<1],siz[N<<1],id[N<<1];
int find(int x) {
return fa[x]==x ? x : fa[x]=find(fa[x]);
}
void uu(int fx,int fy,int goal) {
fx=find(fx),fy=find(fy);
id[fy]=max(id[fx],id[fy]);
if(siz[fx]<=siz[fy]) {
fa[fx]=fy;
if(siz[fx]==siz[fy]) siz[fy]++;
} else {
fa[fy]=fx;
}
}
}
namespace get_lca {
int fa[N<<1],top[N<<1],siz[N<<1],son[N<<1],dep[N<<1],idx[N<<1],js,frm[N<<1];
void dfs1(int u,int f) {
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int topf) {
top[u]=topf;
idx[u]=++js;
frm[js]=u;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(!idx[v]) dfs2(v,v);
}
}
int lca(int x,ll val) {
int ans=x;
while(w[top[x]]>val) ans=top[x],x=fa[top[x]];
int l=idx[top[x]],r=idx[x];
while(l<=r) {
// cout<<l<<" "<<r<<"\n";
int mid=(l+r)>>1;
if(w[frm[mid]]>val) ans=frm[mid],r=mid-1;
else l=mid+1;
}
return ans;
}
void init() {
dfs1(rt,0);
dfs2(rt,rt);
}
}
namespace dij {
struct node {
int v,nxt,q;
}e[N<<1];
int head[N<<1],tot;
priority_queue<pair<ll,int> > q;
void add(int u,int v,int q) {
e[++tot].v=v;
e[tot].q=q;
e[tot].nxt=head[u];
head[u]=tot;
}
void dij() {
q.push(make_pair(0LL,1));
dis[1]=0;
while(!q.empty()) {
pair<ll,int> u=q.top();
q.pop();
if(dis[u.second]!=u.first) continue;
for(int i=head[u.second];i;i=e[i].nxt) {
int v=e[i].v;
if(dis[v]>dis[u.second]+e[i].q) {
dis[v]=dis[u.second]+e[i].q;
q.push(make_pair(dis[v],v));
}
}
}
}
void work() {
memset(dis,0x3f,sizeof(dis));
memset(head,0,sizeof(head));
tot=0;
for(int i=1;i<=m;++i) {
add(edge[i].u,edge[i].v,edge[i].l);
add(edge[i].v,edge[i].u,edge[i].l);
}
dij();
}
}
namespace kruskal {
void work() {
for(int i=1;i<n+n;++i) bcj::fa[i]=i;
for(int i=1;i<n+n;++i)bcj::id[i]=i;
sort(edge+1,edge+1+m);
for(int i=1;i<=n;++i) w[i]=0x3f3f3f3f3f3f3f3fLL;
for(int i=1,js=n;i<=m;++i) {
int fx=bcj::find(edge[i].u),fy=bcj::find(edge[i].v);
if(fx!=fy) {
rt=++js;
add(js,bcj::id[fx]),add(js,bcj::id[fy]);
w[js]=edge[i].a;
bcj::uu(js,fy,js);
bcj::uu(js,fx,js);
if(js==n+n-1) return;
}
}
}
}
void clear() { // 大部分的clear
add_tot=0;
dij::tot=0;
get_lca::js=0;
memset(dij::head,0,sizeof(dij::head));
memset(get_lca::siz,0,sizeof(get_lca::siz));
memset(bcj::siz,0,sizeof(bcj::siz));
memset(head,0,sizeof(head));
memset(dis,0x3f,sizeof(dis));
memset(get_lca::idx,0,sizeof(get_lca::idx));
memset(get_lca::son,0,sizeof(get_lca::son));
}
void dfs(int u,int f) {
dsr[u]=dis[u];
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
dfs(v,u);
dsr[u]=min(dsr[u],dsr[v]);
}
}
void solve() {
dij::work();
kruskal::work();
get_lca::init();
dfs(rt,0);
int Q=read(),k=read();
ll S=read(),lastans=0;
while(Q--) {
ll vv=read(),pp=read();
ll v=(vv+k*lastans-1)%n+1;
ll p=(pp+k*lastans)%(S+1);
int tmp=get_lca::lca(v,p);
lastans=dsr[tmp];
printf("%lld\n",lastans);
}
}
int main() {
// freopen("return.in","r",stdin);
// freopen("return.out","w",stdout);
int T=read();
while(T--) {
n=read(),m=read();
for(int i=1;i<=m;++i) {
edge[i].u=read(),edge[i].v=read();
edge[i].l=read(),edge[i].a=read();
}
clear();
solve();
}
return 0;
}
```
by ComplexPug @ 2019-02-28 22:24:51
只有七十来分
by ComplexPug @ 2019-02-28 22:25:15
dij写错了身败名裂
by ComplexPug @ 2019-03-02 09:05:11