RT,代码如下
#include <bits/stdc++.h>
using namespace std;
struct node {
long long u, v, w, h;
}a[4000000 + 10];
struct com {
long long name, val;
friend bool operator < (com x, com y) {
return x.val < y.val;
}
};
priority_queue <com> q;
com dis[2000000 + 10];
bool vis[2000000 + 10];
long long cnt = 0, fa[2000000 + 10], anc[30][2000000 + 10];
long long last[2000000 + 10], n, m, kal[2000000 + 10];
vector <pair<long long , long long> > head[8000000 + 10];
long long inline found(long long x) {
while (fa[x] != x)
x = fa[x] = fa[fa[x]];
return x;
}
void inline add (long long x, long long y, long long z) {
head[x].push_back(make_pair(y, z));
}
void inline add2 (long long i, long long x, long long y) {
x = found(x); y = found(y); cnt ++;
fa[x] = fa[y] = fa[cnt] = cnt;
kal[cnt] = a[i].h;
add(cnt, x, 0); add(cnt, y, 0);
}
void inline best (long long x) {
long long len = head[x].size(); last[x] = dis[x].val;
if(x <= n) return ;
for(register int i = 0; i < len; i ++) {
long long f = head[x][i].first;
anc[f][0] = x; best(f);
last[x] = min(last[x], last[f]);
}
}
bool cmp (node x, node y) {return x.h > y.h;}
int main () {
long long T, lastans = 0; scanf ("%lld" ,&T);
while (T --) {
memset(last, 0, sizeof(last));
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
scanf("%lld%lld", &n, &m);
for ( register int i = 1; i <= m; i ++) {
scanf("%lld%lld%lld%lld", &a[i].u, &a[i].v, &a[i].w, &a[i].h);
add(a[i].u, a[i].v, i); add(a[i].v, a[i].u, i);
}
long long len = head[1].size(); dis[1].val = 0; vis[1] = true;
for(register int i = 1; i <= n; i ++) dis[i].name = i;
for(register int i = 0; i < len; i ++) {
long long x = head[1][i].first, y = head[1][i].second;
dis[x].val = a[y].w; q.push(dis[a[y].v]);
}
printf("\n");
while(!q.empty()) { //cout<<1;
com top = q.top();
if(vis[top.name] || dis[top.name].val != top.val)
{q.pop(); continue;}
len = head[top.name].size(); vis[top.name] = true;
for(register int i = 0 ; i < len; i ++) {
long long x = head[top.name][i].first, y = head[top.name][i].second;
if(dis[x].val > dis[top.name].val + a[y].w) {
dis[x].val = dis[top.name].val + a[y].w;
if(!vis[x]) q.push(dis[x]);
}
}
}
sort(a + 1, a + m + 1, cmp); cnt = n;
for(register int i = 1; i <= n + m; i ++) fa[i] = i;
for(register int i = 1; i <= m; i ++)
if(found(a[i].u) != found(a[i].v))
add2(i, a[i].u, a[i].v);
best(cnt);
// for(register int i= 1; i <= cnt; i ++)
// cout<<last[i]<<endl;
for(register int i = 1; (1 << i) <= cnt; i ++)
for(register int j = 1; j <= cnt ; j++)
anc[j][i] = anc[anc[j][i -1]][i-1];
long long Q, K, S; scanf("%lld%lld%lld", &Q, &K, &S);
for(register int i = 1 ; i <= Q; i ++) {
long long v0, p0; scanf("%lld%lld", &v0, &p0);
v0 = (v0 + K * lastans - 1) % n + 1;
p0 = (p0 + K * lastans) % (S + 1);
for(register int j = 22; j >= 0; j --)
if(anc[v0][j] && kal[anc[v0][j]] > p0)
v0 = anc[v0][j];
// cout<<v0<<endl;
printf("%lld\n", last[v0]); lastans = last[v0];
}
}
}