[NOI2018]归程

[NOI2018]归程
这题我只会离线做法..在线做法的克鲁斯卡尔重构树我虽然会但是…我不会倍增…所以就比较困难,于是暂时先只写了离线做法.
这个题其实是一个动态的图上的最短路问题.

从$1$号点开始跑一遍 Dijkstra,求出到每个节点的最短路
然后问题就转化成了在开车能到达的点里选择一个dis最小的点
开车能到达的点用克鲁斯卡尔重构树来维护,每次要查询的就是
重构树上对应合并节点的子树节点中的dis最小值,寻找对应节点用树上倍增解决
子树dis最小值随便搞一搞都可以.当然这是正解做法.
而离线做法就不需要重构树,只需要把询问排一下序.
然后根据海拔的单调性用加权并查集维护答案就行了.
$Code:$

/*
从 1号点开始跑一遍 Dijkstra,求出到每个节点的最短路
然后问题就转化成了在开车能到达的点里选择一个dis最小的点
开车能到达的点用克鲁斯卡尔重构树来维护,每次要查询的就是
重构树上对应合并节点的子树节点中的dis最小值,寻找对应节点用树上倍增解决
子树dis最小值随便搞一搞都可以.

But this code is not for online algorithm.Because of my own ability.
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define pii pair < int , int >
#define rint read<int>

using std::pair ;
using std::priority_queue ;

const int N = 2e5 + 5 ;
const int M = 4e5 + 5 ;

template < class T >
    inline T min (T __A , T __B) { return __A < __B ? __A : __B ; }

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
        while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
        }
        return f * x ;
    }

struct edge { int from , to , data , height , next ; } e[(M<<1)] ;

struct query { int st , p , order , ans ; } opt[M] ;

priority_queue < pii , std::vector < pii > , std::greater < pii > > q ;
int T , n , m , head[N] , f[N][2] , dis[N] , Q , k , s , cnt ;

inline void Dijkstra (int cur) {
    memset ( dis , 0x3f , sizeof ( dis ) )  ;
    dis[cur] = 0 ; q.push ( { dis[cur] , cur } ) ;
    while ( ! q.empty () ) {
        int j = q.top ().second ;
        if ( dis[j] != q.top ().first ) { q.pop () ; continue ; }
        q.pop () ;
        for (int i = head[j] ; i ; i = e[i].next) {
            int t = e[i].to ;
            if ( dis[t] > dis[j] + e[i].data ) {
                dis[t] = dis[j] + e[i].data ;
                q.push ( { dis[t] , t } ) ;
            }
        }
    }
    return ;
}

inline int getf (int x) { return f[x][0] == x ? x : ( f[x][0] = getf ( f[x][0] ) ) ; }

inline void merge (int u , int v) {
    int x = getf ( u ) , y = getf ( v ) ;
    if ( x != y ) {
        f[y][0] = x ;
        f[x][1] = min ( f[y][1] , f[x][1] ) ;
    }
    return ;
}

inline void init () {
    for (int i = 1 ; i <= n ; ++ i) { f[i][0] = i ; f[i][1] = dis[i] ; }
    return ;
}

inline bool cmp (edge a , edge b) { return a.height > b.height ; }

inline bool CMP (query a , query b) { return a.p > b.p ; }

inline void build (int u , int v , int len , int h){
    e[++cnt].next = head[u] ; e[cnt].from = u ; e[cnt].to = v ;
    e[cnt].height = h ; head[u] = cnt ; e[cnt].data = len ; return ;
}

inline bool Cmp (query a , query b) {  return a.order < b.order ; }

int main () {
    T = rint () ;
    while ( T -- ) {
        cnt = 0 ;
        n = rint () ; m = rint () ; memset ( head , 0 , sizeof ( head ) ) ;
        for (int i = 1 , u , v , l , h ; i <= m ; ++ i) {
            u = rint () ; v = rint () ; l = rint () ; h = rint () ;
            build ( u , v , l , h ) ; build ( v , u , l , h ) ;
        }
        Dijkstra ( 1 ) ; init () ;
        Q = rint () ; k = rint () ; s = rint () ;
        for (int i = 1 , u , v ; i <= Q ; ++ i) {
            u = rint () ; v = rint () ;
            opt[i].st = ( u - 1 ) % n + 1 ;
            opt[i].p = v % ( s + 1 ) ;
            opt[i].order = i ;
        }
        std::sort ( e + 1 , e + cnt + 1 , cmp ) ;
        std::sort ( opt + 1 , opt + Q + 1 , CMP ) ;
        for (int i = 1 , last = 1 ; i <= Q ; ++ i) {
            for (int j = last ; e[j].height > opt[i].p && j <= cnt ; ++ j) {
                merge ( e[j].from , e[j].to ) ; last = j ;
                if ( e[j].height <= opt[i].p ) break ;
            }
            opt[i].ans = f[getf(opt[i].st)][1] ;
        }
        std::sort ( opt + 1 , opt + Q + 1 , Cmp ) ;
        for (int i = 1 ; i <= Q ; ++ i) printf ("%d\n" , opt[i].ans ) ;
    }
    return 0 ;
}