• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            #include <cstdio>
            #include 
            <vector>
            #include 
            <bitset>
            #include 
            <queue>

            using namespace std;

            int abs( int a, int b )
            {
                
            return a> b? a- b: b- a;
            }

            struct Point
            {
                
            int x, y;
                Point(){}
                Point( 
            int a, int b ): x(a), y(b) {}
            };

            struct Node
            {
                
            int u, total;
                bitset
            <12> state;

                Node(){}
                Node( 
            int a, int b, bitset<12> c ): u(a), total(b), state(c) {}
            };

            int   r, c,result,n;
            vector
            <Point> map;
            bool visite[25][25];
            int  graph[15][15];

            void bfs()
            {
                queue
            <Node> q;
                bitset
            <12> t; t.reset ();

                q.push( Node( 
            00, t ) ); 

                
            while!q.empty() )
                {
                    
            int u= q.front().u, total= q.front().total;
                    bitset
            <12> state= q.front().state; q.pop();

                    
            bool ok= true;
                    
            forint i= 0; i<=  n; ++i )
                        
            if( state[i]== 0 ) ok= false;

                    
            if( ok  )
                    {
                        
            if( total+ graph[u][0]< result ) result= total+ graph[u][0];

                        
            continue;
                    }

                    
            forint i= 0; i<= n; ++i )
                    {
                        bitset
            <12> t= state;

                        
            if( t[i]== 0 && total+ graph[u][i]< result )
                        {
                            t[i]
            = 1;

                            q.push( Node( i, total
            + graph[u][i], t ) );
                        }
                    }
                }
            }

            int main()
            {
                
            int test;
                scanf(
            "%d",&test);

                
            while( test-- )
                {
                    map.clear();
                    scanf(
            "%d%d",&r,&c);

                    
            int a,b;
                    scanf(
            "%d%d",&a,&b);  map.push_back( Point( a, b ) );

                    scanf(
            "%d",&n );
                    
            forint i= 0; i< n; ++i )
                    {
                        scanf(
            "%d%d",&a,&b);

                        map.push_back( Point(a,b) );
                    }

                    
            for( size_t i= 0; i< map.size(); ++i )
                        
            for( size_t j= 0; j< map.size(); ++j )
                            graph[i][j]
            = abs( map[i].x- map[j].x )+ abs( map[i].y- map[j].y );

                    result
            = 1<<30;

                    bfs();
                    printf(
            "The shortest path has length %d\n", result );
                }

                
            return 0;
            }

            posted on 2008-12-24 20:22 Darren 閱讀(131) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            三级三级久久三级久久| 久久九九全国免费| 日韩欧美亚洲综合久久| 久久久噜噜噜久久中文字幕色伊伊| 色妞色综合久久夜夜| 成人国内精品久久久久影院| Xx性欧美肥妇精品久久久久久| 久久人人爽人人爽人人片AV东京热| 伊人久久大香线蕉AV色婷婷色| 久久精品国产亚洲网站| 久久精品一本到99热免费| 91精品国产91久久久久久| 久久精品国产免费观看| 亚洲国产二区三区久久| 尹人香蕉久久99天天拍| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久精品国产第一区二区三区| 国产精品久久久久天天影视| 亚洲精品无码久久久久AV麻豆| 国产精品久久毛片完整版| 色老头网站久久网| 久久国产香蕉视频| 嫩草影院久久99| 精品九九久久国内精品| 色欲久久久天天天综合网精品| 久久精品亚洲福利| 国内精品久久久久久久coent| 97久久国产亚洲精品超碰热| 性欧美大战久久久久久久久| 久久综合日本熟妇| 久久久久久极精品久久久 | 99久久精品免费看国产一区二区三区 | 精品久久亚洲中文无码| 人妻无码久久精品| 久久精品国产精品亚洲| 91精品免费久久久久久久久| 久久香蕉一级毛片| 99久久久久| 亚洲精品国产自在久久| 久久久亚洲裙底偷窥综合| 97精品伊人久久大香线蕉|