zoj3016.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std; 
const int maxn = 1210;
const int maxlen = maxn * maxn;
const int maxN = 601;
const int inf  = 0x3fffffff; 

int lx[ maxn ], ly[ maxn ], n, m, N ;
int ls[ maxN ][ 5 ] ; 
int toDown[maxn][maxn], toRight[maxn][maxn]; 

void readr ()
{
        n = m = 0; scanf("%d", &N);
        int i, j, k;
        for( i = 0; i < N; ++ i ){
                for( j = 0; j < 5; ++ j ) scanf("%d", ls[i] + j ) ;
                lx[n++] = ls[i][0], lx[n++] = ls[i][2];
                ly[m++] = ls[i][1], ly[m++] = ls[i][3];
        }
        sort( lx, lx+n ) ; n = unique( lx, lx+n ) - lx;
        sort( ly, ly+m ) ; m = unique( ly, ly+m ) - ly;
        for( i = 0; i < N; ++ i ) {
                ls[i][0] = lower_bound( lx, lx+n, ls[i][0] ) - lx;
                ls[i][1] = lower_bound( ly, ly+m, ls[i][1] ) - ly;
                ls[i][2] = lower_bound( lx, lx+n, ls[i][2] ) - lx;
                ls[i][3] = lower_bound( ly, ly+m, ls[i][3] ) - ly;
                if( ls[i][0] > ls[i][2] ) swap ( ls[i][0], ls[i][2] );
                if( ls[i][1] > ls[i][3] ) swap ( ls[i][1], ls[i][3] );
        }
        ++ n, ++ m ;
        memset( toDown, 0, sizeof( toDown ) );
        memset( toRight, 0, sizeof( toRight ) );
        for( i = 0; i < N; ++ i )
                if( ls[i][0] == ls[i][2] ) {
                        for( j = ls[i][1]+1; j <= ls[i][3]; ++ j ) toDown[ls[i][0]][j] = ls[i][4];
                } else if( ls[i][1] == ls[i][3] ) {
                        for( j = ls[i][0]+1; j <= ls[i][2]; ++ j ) toRight[j][ls[i][1]] = ls[i][4];
                } ;
} 

int value[ maxlen ], heap[ maxlen ], ps[ maxlen ], len;

bool mk[ maxlen ];  

void HeapUp ( int r )
{
        int q = ps[r], p = q >> 1;
        while( p && value[heap[p]] > value[r] ) {
                ps[heap[p]] = q; heap[q] = heap[p];
                q = p; p = q >> 1;
        }
        heap[q] = r; ps[r] = q;
} 

int getmin ()
{
        int ret = heap[1], p = 1, q = 2, r = heap[len--];
        while( q < len ) {
                if( q < len && value[heap[q+1]] < value[heap[q]] ) q ++ ;
                if( value[heap[q]] < value[r] ) {
                        ps[heap[q]] = p; heap[p] = heap[q];
                        p = q; q = p << 1;
                } else break;

        }
        heap[p] = r; ps[r] = p;
        return ret;
} 

const int move[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; 

struct Point
{
        int x, y ;
        Point () {};
        Point ( int _x, int _y ) { x = _x, y = _y; };
        Point ( int t ) { x = t / m, y = t % m; };
        int zip () const { return x * m + y ; };
        bool inrange() const { return x >= 0 && x < n && y >= 0 && y < m; };  
        Point mov ( int d ) { return Point( x + move[d][0] , y + move[d][1] ) ; };
}; 

void update ( const Point &ps , const int cost )
{
        int zp = ps.zip ();
        if( !mk[zp] && value[zp] > cost ) {
                value[zp] = cost;
                HeapUp( zp ) ;
        }
} 

void solvr ()
{
        int i, j, k;
        for( len = i = 0; i < n * m ; ++ i ) { heap[++len] = i; value[i] = inf; ps[i] = len; mk[i] = 0; };
        value[0] = 0;
        long long ans = 0;
        while( len > 0 )
        {
                int t = getmin (); mk[t] = 1;
                ans += value[t] ;
                Point old( t ), now;
// right
                now = old.mov( 0 );
                if( now.inrange () ) update ( now, toRight[old.x][old.y] );
// left
                now = old.mov( 1 );
                if( now.inrange () ) update ( now, toRight[now.x][now.y] );
// down
                now = old.mov( 2 );
                if( now.inrange () ) update ( now, toDown[old.x][old.y] );
// up
                now = old.mov( 3 );
                if( now.inrange () ) update ( now, toDown[now.x][now.y] ); 
      } 
        printf("%lld\n", ans);
} 

int main ()
{
        int cases, index;
        scanf("%d", &cases);
        for ( index = 0; index < cases; ++ index ) {
                readr ();
                solvr ();
        }
        return 0 ;

}