P4768 [NOI2018]归程

题目描述

给出 $N, M$ 的无向图, 每条边有海拔和长度两个权值, 每次询问给出水位线,起点, 问从起点出发到 $1$ 号节点的最小步行距离

路程 = 开车路程+步行路程
经过海拔不大于水位线的边需要弃车

Solution

以海拔建克鲁斯卡尔重构树
其中使用 $nst[]$ 表示每个树节点上方的重构树节点
预处理出 $1$ 节点到每个节点的最短路
预处理出重构树中每个节点子树中离 $1$ 节点最近的距离 $min\_son$
倍增求出能够到达的最高的克鲁斯节点
输出该节点中最短距离 $min\_son$

Addition

预处理倍增数组方法
以重构树最上方的节点为根 $DFS$ , 分两种情况

重构树节点:
- 赋予此节点 $Fk[][]$ 倍增数组并更新
- 更新 $DFS$ 的 $fa$ 参数
原树节点:

$min\_son[]$ 赋值
$nst[]$ 值为上方传下的 $fa$
传递 $DFS$ 的 $fa$ 参数

Attention

一定要初始化 $nst$ 数组!!!
还有倍增数组…

Code

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 600005;
const int inf = 0x7f7f7f7f;

int N, M, K, Q, S, last_ans, Lim;
std::bitset <maxn> Used;
int head[maxn], F[maxn], w[maxn], Fk[maxn][22];
int Dis[maxn], min_son[maxn], nst[maxn];
int cnt, num0;

struct Edge{ int nxt, to, dis, high; } edge[maxn<<2];
struct Edg{ int u, v, dis, high; } Ed[maxn<<1];

void Add(int from, int to, int dis, int high){
        edge[num0] = (Edge){ head[from], to, dis, high };
        head[from] = num0 ++;
}

bool cmp0(Edg a, Edg b){ return a.high > b.high; }

int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); };

void DFS(int k, int fa, int last){
        if(k <= N) min_son[k] = Dis[k];
        else{
                Fk[k][0] = fa;
                min_son[k] = 0x7f7f7f7f; 
                for(reg int i = 1; i <= 20; i ++) Fk[k][i] = Fk[Fk[k][i-1]][i-1];
        }
        for(reg int i = head[k]; ~i; i = edge[i].nxt){
                if(i < Lim) continue ;
                int to = edge[i].to;
                if(to == last) continue ;
                if(k > N) DFS(to, k, k); 
                else DFS(to, fa, k);
                min_son[k] = std::min(min_son[k], min_son[to]);
        }
}

int Get_Ans(){
        int v0 = read(), p0 = read();
        v0 = ( (1ll*v0 + K*last_ans - 1) % N ) + 1; //注意这里的long long
        p0 = (1ll*p0 + K*last_ans) % (S + 1);
        int t = nst[v0];
        w[0] = 0, min_son[0] = 0x7f7f7f7f;
        for(reg int i = 20; i >= 0; i --)
                if(w[Fk[t][i]] > p0) t = Fk[t][i];
        if(w[t] <= p0) return last_ans = min_son[v0];
        return last_ans = min_son[t];
}

void Dijstra(){
        memset(Dis, 0x7f, sizeof Dis);
        typedef std::pair<int, int> pr;
        Used.reset();
        std::priority_queue <pr, std::vector<pr>, std::greater<pr> > Q;
        Q.push(pr(0, 1)), Dis[1] = 0;
        while(!Q.empty()){
                int t = Q.top().second; Q.pop();
                if(Used.test(t)) continue ;
                Used.set(t, 1);
                for(reg int i = head[t]; ~i; i = edge[i].nxt){
                        int to = edge[i].to;
                        if(Dis[to] == inf || Dis[to] > Dis[t] + edge[i].dis){
                                Dis[to] = Dis[t] + edge[i].dis; 
                                Q.push(pr(Dis[to], to));
                        }
                }
        }
}

void Kurskal(){ 
        memset(nst, 0, sizeof nst);             //一定要初始化!!!
        for(reg int i = 0; i <= (N<<1)+1; i ++) F[i] = i;
        std::sort(Ed+1, Ed+M+1, cmp0); 
        Lim = num0;
        int num1 = 0, cnt = N; 
        for(reg int i = 1; i <= M; i ++){
                int t1 = Find(Ed[i].u), t2 = Find(Ed[i].v);
                if(t1 == t2) continue ; 
                w[++ cnt] = Ed[i].high;
                F[t1] = F[t2] = cnt;
                Add(cnt, t1, 0, 0), Add(cnt, t2, 0, 0); 
                if(!nst[Ed[i].u]) nst[Ed[i].u] = cnt;
                if(!nst[Ed[i].v]) nst[Ed[i].v] = cnt;
                if(++ num1 == N-1) break ; 
        }
        memset(Fk, 0, sizeof Fk);               //记得初始化
        DFS(cnt, cnt, 0);
}

void Input(){
        memset(head, -1, sizeof head);
        last_ans = num0 = 0;
        N = read(), M = read();
        int u, v, l, a; 
        for(reg int i = 1; i <= M; i ++){ 
                u = read(), v = read(), l = read(), a = read();
                Ed[i] = (Edg){ u, v, l, a }; 
                Add(u, v, l, a), Add(v, u, l, a); 
        } 
}

void Work(){
        Input();
        Dijstra();
        Kurskal();

        Q = read(), K = read(), S = read();
        while(Q --) printf("%d
", Get_Ans());
}

int main(){
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}