• <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   管理


            亚洲精品综合久久| 久久久久无码精品| 久久97久久97精品免视看| 久久精品国产WWW456C0M| 久久综合色之久久综合| 777米奇久久最新地址| 91久久精品国产成人久久| 一本一本久久a久久精品综合麻豆| 亚洲欧美国产日韩综合久久| 中文国产成人精品久久不卡| 精品综合久久久久久97超人 | 亚洲国产精品综合久久网络 | 国产精品成人99久久久久91gav| 亚洲精品国产第一综合99久久| 久久国产精品99国产精| 亚洲国产成人乱码精品女人久久久不卡| 久久精品一区二区三区AV| 亚洲欧洲久久久精品| AV色综合久久天堂AV色综合在| 国内高清久久久久久| 久久国产视频网| 久久久综合九色合综国产| 久久免费小视频| 久久久亚洲欧洲日产国码aⅴ| 伊人久久精品影院| 久久久免费观成人影院| 99久久精品国产综合一区| 久久亚洲精品中文字幕| 国产精品久久影院| 午夜天堂av天堂久久久| 久久精品水蜜桃av综合天堂| 国产精品久久久久久久久软件| 综合久久精品色| 欧美大战日韩91综合一区婷婷久久青草 | 国产成年无码久久久免费| 亚洲午夜无码AV毛片久久| 久久亚洲精品无码观看不卡| 久久夜色精品国产亚洲av| 久久精品国产精品亚洲人人| 久久久久久国产精品无码下载| 国产午夜精品久久久久九九电影|