APIO2015 Bali Sculptures UOJ111 BZOJ4070

好像大家的做法都是最短路。
由于边权都是1嘛，所以我就二五二五的动手bfs了……
但是纯搜好像是不行的，大家还好心提醒我uoj卡的很严，会TLE，所以我就用了一些bool数组记录，要是算过了就不再算了（这好像是废话2333）
由于刚学了莫队算法（不知道莫队的戳这里），所以对分块思想的印象比较深，于是就开始分块水这个题目23333
大概做法是取一个限制ss，如果狗跳的距离小于ss，就用数组记下来；否则就直接不管那么多跳就行了（一共30000/ss次）
（因为数组开太大会MLE的2333所以就分块啊）

具体细节的处理放在注释

#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std ;
bool Read ( int &x ) {
    x = 0 ; char c = getchar() ; bool f = 0 ;
    while ( !isdigit(c) ) {
        if ( c == '-' ) f = 1 ;
        if ( c == EOF ) return false ;
        c = getchar() ;
    }
    while ( isdigit(c) ) {
        x = 10*x + c - '0' ;
        c = getchar() ;
    } if (f) x = -x ;
    return true ;
} //读入优化不解释
const int ss = 110 ; // 随便一个限制
const int maxn = 30005 ;
struct node {
    int dir, lenth, tim, now ;
    //当前狗的方向、步长；现在跳了几步、在那个房子上
} s[maxn] ;
queue <node> q ;
int n, m, A[maxn], B[maxn] ;
bool mark[maxn][ss+1], mk[maxn] ;
//mark[i][j]代表：在点i开始一只步长为j的狗
//mk[i]代表：点i
//都指示是否被计算过
vector <int> G[maxn] ;
//G[i]存储所有的步长，由于可能有一些狗步长一样，所以就不记录狗
void update ( int x, int tim ) { //换条狗
    if ( mk[x] ) return ;
    mk[x] = 1 ;
    int i, j, siz = G[x].size(), u, len ;
    for ( i = 0 ; i < siz ; i ++ ) {
        len = G[x][i] ;
        if ( x+len==A[2] || x-len==A[2] ) {
            printf ( "%d\n", tim+1 ) ;
            exit(0) ;
            //跳到终点了，直接再见
        }
        if ( len <= ss ) {
            if ( mark[x][len] ) continue ;
            mark[x][len] = 1 ;
            //限制内，需要更新标记
        }
        if ( x+len <= m ) q.push( (node){1, len, tim+1, x+len} ) ;
        if ( x-len >= 1 ) q.push( (node){0, len, tim+1, x-len} ) ;
    }
}
int bfs() {
    int i, u, x, tim, len, siz ;
    if ( A[1] == A[2] ) return 0 ;
    while ( !q.empty() ) q.pop() ;
    update ( A[1], 0 ) ;
    while ( !q.empty() ) {
        node tmp = q.front() ;
        q.pop() ;
        x = tmp.now, len = tmp.lenth, tim = tmp.tim ;
        if ( x+len == A[2] || x-len == A[2] ) return tim+1 ;
        update ( x, tim ) ;
        //将所有相关的狗的情况都放进bfs队列
        if ( len <= ss ) {
            //限制范围内
            if ( tmp.dir ) {
            //向编号大的方向跳
                if ( x+len <= m && !mark[x][len] )
                    q.push( (node){1, len, tim+1, x+len} ) ;
                mark[x][len] = 1 ;
            } else {
                if ( x-len >= 1 && !mark[x][len] ) 
                    q.push( (node){0, len, tim+1, x-len} ) ;
                mark[x][len] = 1 ;
            }
        } else {
            if ( tmp.dir == 0 && x-len >= 1 ) 
                q.push( (node){0, len, tim+1, x-len} ) ;
            else if ( x+len <= m ) 
                q.push( (node){1, len, tim+1, x+len} ) ;
        }
    }
    return -1 ;
}
int main() {
    int i, j, k ;
    Read(m) ; Read(n) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(A[i]) ; Read(B[i]) ;
        ++ A[i] ;
        //个人习惯将点从1~n编号
    }
    for ( i = 1 ; i <= n ; i ++ ) 
        G[A[i]].push_back(B[i]) ;
    printf ( "%d\n", bfs() ) ;
    return 0 ;
}