Luogu

分析

考虑把边按海拔从大到小排序并建 Kruskal 重构树。

每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$，则子树 $u$ 中的点是可以开车到达的，找一个到 $1$ 的距离最小的点即可。

一遍 Dijkstra（关于 SPFA：它死了）预处理出每个点到 $1$ 的最短路，在重构树上维护子树最值即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

int n,m;

struct edge { int u,v,l,a; } e[N];
bool operator <(edge a,edge b) { return a.a>b.a; }
vector<pair<int,int> > E[N];
vector<int> T[N];

struct node { int u,d; };
bool operator <(node a,node b) { return a.d>b.d; }
int dis[N];
void dijkstra() {
    priority_queue<node> Q; Q.push((node){1,0});
    memset(dis,0x3f,sizeof(dis)); dis[1]=0;
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (auto t:E[u]) { int v=t.first,w=t.second;
            if (d+w<dis[v]) Q.push((node){v,dis[v]=d+w});
        }
    }
}

struct dsu {
    int f[N];
    int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
} U;

int f[19][N],height[N],mindis[N];
void dfs(int u,int fa) {
    f[0][u]=fa;
    for (int i=1;i<=18;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (int v:T[u]) dfs(v,u),mindis[u]=min(mindis[u],mindis[v]);
}
int jump(int u,int lim) {
    for (int i=18;~i;--i)
        if (height[f[i][u]]>lim) u=f[i][u];
    return u;
}
void build() {
    sort(e+1,e+m+1); int tot=n;
    for (int i=1;i<n<<1;++i) U.f[i]=i,T[i].clear();
    for (int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v;
        if (U.find(u)!=U.find(v)) {
            height[++tot]=e[i].a;
            T[tot].emplace_back(U.find(u)),U.f[U.find(u)]=tot;
            T[tot].emplace_back(U.find(v)),U.f[U.find(v)]=tot;
        }
    }
    for (int i=1;i<=n;++i) mindis[i]=dis[i];
    for (int i=n+1;i<=tot;++i) mindis[i]=2e9;
    dfs(tot,0);
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read();
        for (int i=1;i<=n;++i) E[i].clear();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read(),l=read(),a=read();
            e[i]=(edge){u,v,l,a};
            E[u].emplace_back(mp(v,l));
            E[v].emplace_back(mp(u,l));
        }
        dijkstra(); build();
        int Q=read(),K=read(),S=read();
        int lastans=0;
        while (Q--) {
            int v=(read()+K*lastans-1)%n+1;
            int p=(read()+K*lastans)%(S+1);
            printf("%d\n",lastans=mindis[jump(v,p)]);
        }
    }
    return 0;
}
最后修改：2020 年 06 月 01 日 07 : 52 PM
© 允许规范转载