ZROI#961-白红宇

ZROI#961

阅读量：5288 次

发布时间：2019-06-14

本文共 5605 字，大约阅读时间需要 18 分钟。

很诡异地一道题,你看他问的是是否存在距离\(d\in [dist,1.1dist]\)的路径.

你想一下这个\(1.1\)是个啥.好像不知道,先考虑暴力叭.

暴力你就\(bfs\),让点重复入队就好了,每个点维护一个\(set\),查询直接\(lower\_bound\)即可.

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read
                
                 #define int long long#define pb push_backusing std::queue ;using std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;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 ;}const int N = 2e5 + 100 ;struct edge { int to , next ; double data ; } e[N<<1] ;set < double > p[N] ;int n , m , Q , tot , head[N] ;double dis[N] ;bool vis[N] ;inline void build (int u , int v , double w) { e[++tot].next = head[u] ; e[tot].to = v ; e[tot].data = w ; head[u] = tot ; return;}queue < int > q ;inline void bfs (int cur) { vis[cur] = true ; q.push ( cur ) ; dis[cur] = 0 ; p[cur].insert ( dis[cur] ) ; while ( ! q.empty () ) { int j = q.front () ; q.pop () ; vis[j] = false ; for (int i = head[j] ; i ; i = e[i].next) { int k = e[i].to ; for (auto it : p[j]) { double dist = it + e[i].data ; if ( p[k].find ( dist ) == p[k].end () ) { if ( ! vis[k] ) { q.push ( k ) ; vis[k] = true ; } p[k].insert ( dist ) ; } } } } return ;}signed main (int argc , char * argv[]) { n = rint () ; m = rint () ; Q = rint () ; rep ( i , 1 , m ) { int u = rint () , v = rint () , w = rint () ; build ( u , v , w ) ; } bfs ( 1 ) ; while ( Q -- ) { int k = rint () ; double dist ; scanf ("%lf" , & dist ) ; auto pos = p[k].lower_bound ( dist ) ; if ( pos == p[k].end () ) puts ("NO") ; else if ( *pos <= dist * 1.1 ) puts ("YES") ; else puts ("NO") ; } return 0 ;}

然后我们发现,这个玩意儿的瓶颈在于转移的时候状态太多了.

然后我们考虑优化这个东西.

我们发现,如果说有三个距离\(x,y,z\)满足以下条件:

\[\cfrac{z}{1.1}<x<y<z\]

那么\(y\)就是没用的,显然答案的存在性不会因为缺少\(y\)而改变.

于是我们每次合并两个距离集合(即上述代码的转移,本质是两个距离集合的合并)就可以把这些\(y\)踢掉,使用类似于归并排序的思路即可解决.

这样你可能会认为还是会\(TLE\),但实际上它的复杂度是对的,为什么呢?

因为\(1.1^{450}\)远远大于了所有权值的总和\(10^{18}\),也就是说一个点最多同时有\(450\)个状态被保留.

每次合并就是\(\Theta(450)\)的,查询随意,怎么搞都能过.

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)#define pii pair < int , int >#define one first#define two second#define rint read
                
                 #define int long long#define pb push_back#define db doubleusing std::queue ;using std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;using std::lower_bound ;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 ;}const int N = 2e5 + 100 ;const int M = 477 ;struct edge { int to , next ; double data ; } e[N] ;queue < int > q ; double tmp[N] , dis[N][M] ;int n , m , Q , tot , head[N] , cnt[N] , deg[N] ;inline void build (int u , int v , double w) { e[++tot].next = head[u] ; e[tot].to = v ; e[tot].data = w ; head[u] = tot ; return;}inline void merge (int x , int y , double val) { // 从 x 到 y int l = 1 , r = 1 , now = 0 ; while ( l <= cnt[x] && r <= cnt[y] ) { double cur = dis[x][l] + val ; if ( cur < dis[y][r] ) { while ( now >= 2 && (db)cur <= (db)tmp[now-1] * 1.1 && cur >= tmp[now] ) -- now ; tmp[++now] = cur ; ++ l ; } else { while ( now >= 2 && (db)dis[y][r] <= (db)tmp[now-1] * 1.1 && dis[y][r] >= tmp[now] ) -- now ; tmp[++now] = dis[y][r] ; ++ r ; } } while ( l <= cnt[x] ) { double cur = dis[x][l] + val ; while ( now >= 2 && (db)cur <= (db)tmp[now-1] * 1.1 && cur >= tmp[now] ) -- now ; tmp[++now] = cur ; ++ l ; } while ( r <= cnt[y] ) { while ( now >= 2 && (db)dis[y][r] <= (db)tmp[now-1] * 1.1 && dis[y][r] >= tmp[now] ) -- now ; tmp[++now] = dis[y][r] ; ++ r ; } rep ( i , 1 , now ) dis[y][i] = tmp[i] ; cnt[y] = now ; return ;}inline void SPFA (int cur) { rep ( i , 1 , n ) if ( ! deg[i] ) q.push ( i ) ; ++ cnt[cur] ; dis[cur][cnt[cur]] = 0.0 ; while ( ! q.empty () ) { int j = q.front () ; q.pop () ; for (int i = head[j] ; i ; i = e[i].next) { int k = e[i].to ; -- deg[k] ; merge ( j , k , e[i].data ) ; if ( ! deg[k] ) q.push ( k ) ; } } return ;}signed main (int argc , char * argv[]) { n = rint () ; m = rint () ; Q = rint () ; rep ( i , 1 , m ) { int u = rint () , v = rint () ; db w ; scanf ("%lf" , & w ) ; build ( u , v , w ) ; ++ deg[v] ; } SPFA ( 1 ) ; while ( Q -- ) { int k = rint () , dist = rint () ; int pos = lower_bound ( dis[k] + 1 , dis[k] + cnt[k] + 1 , dist ) - dis[k] ; if ( (db)dis[k][pos] > (db)1.1 * dist || pos == cnt[k] + 1 ) puts ("NO") ; else puts ("YES") ; } return 0 ;}