这题我只会离线做法..在线做法的克鲁斯卡尔重构树我虽然会但是...我不会倍增...所以就比较困难,于是暂时先只写了离线做法.
这个题其实是一个动态的图上的最短路问题.
从
\(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 #include #include #include #include #include #define pii pair < int , int >#define rint read 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 ;}
\(Updated on 9.3:\)
满分思路上面说啦,时隔12天,我终于
\(AC\)了这道题,哭哭~
\(Code:\) #include #include #include #include #include #include #include #include #include #include #include