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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋

            題目地址:
                     http://acm.hdu.edu.cn/showproblem.php?pid=1548
            題目描述:
            A strange lift
            Time Limit: 
            2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
            Total Submission(s): 
            2641    Accepted Submission(s): 944


            Problem Description
            There 
            is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can't go up high than N,and can't go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can'do it, because it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist.
            Here comes the problem: when you 
            is on floor A,and you want to go to floor B,how many times at least he havt to press the button "UP" or "DOWN"?

             

            Input
            The input consists of several test cases.,Each test 
            case contains two lines.
            The first line contains three integers N ,A,B( 
            1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,.kn.
            A single 
            0 indicate the end of the input.
             

            Output
            For each 
            case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can't reach floor B,printf "-1".
             

            Sample Input
            5 1 5
            3 3 1 2 5
            0
             

            Sample Output
            3

            題目分析:
                    這題又是一個標準的  Dijkstra 算法的題目 ( 最短路 ).  要說難度嗎?  對我而言吧, 就是 圖的生成.
            剛開始做的時候自己想復雜了, 以為從不同的樓層開始, 就有不同的走法, 所以開始的時候寫循環沒寫對,
            就寫成了遞歸.   結果很杯具的 STACK_OVERFLOW........   在 AMB 神牛的指點發現, 原來是自己想復雜了,
            只需要計算出每一個樓層的 上樓 和 下樓就可以了, 當然, 要注意是否越界.  圖生成后, 當然就是 DIJKSTRA了.

            閑來無事, 又復制一遍 :
                        Dijkstra算法的基本思路是:

                     假設每個點都有一對標號 (dj, pj),其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路),其長度等于零);

            pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下:

              1) 初始化。起源點設置為:① ds=0, ps為空;② 所有其他點: di=∞, pi=?;③ 標記起源點s,記k=s,其他所有點設為未標記的。

              2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離,并設置:


            dj=min[dj, dk+lkj]


            式中,lkj是從點k到j的直接連接距離。

              3) 選取下一個點。從所有未標記的結點中,選取dj 中最小的一個i:


            di=min[dj, 所有未標記的點j]


            點i就被選為最短路徑中的一點,并設為已標記的。

              4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*,作為前一點,設置:i=j*

              5) 標記點i。如果所有點已標記,則算法完全推出,否則,記k=i,轉到2) 再繼續。



            代碼如下:
            #include <iostream>
            using namespace std;
            const int MAX = 200;
            const int INF = 0x7FFFFFF;
            int N,A,B;
            int g[MAX+1][MAX+1];
            int hash[MAX+1];
            int path[MAX+1];
            int K[MAX+1];
            int Dijkstra ( int beg , int end )
            {
                path[beg] 
            = 0;
                hash[beg] 
            = false;
                
            while ( beg != end )
                {
                        
            int m = INF, temp;
                        
            for ( int i = 1; i <= N; ++ i )
                        {
                              
            if ( g[beg][i] != INF )
                                   path[i] 
            = min ( path[i], path[beg] + g[beg][i] );
                              
            if ( m > path[i] && hash[i] )
                              {
                                   m 
            = path[i];
                                   temp 
            = i; 
                              }           
                        }
                        beg 
            = temp;
                        
            if ( m == INF )
                             
            break;
                        hash[beg] 
            = false;
                }
                
            if ( path[end] == INF )
                     
            return -1;
                
            return path[end]; 
            }

            int main ()
            {
                
            while ( scanf ( "%d%d%d"&N, &A, &B ) , N )
                {
                        
            for ( int i = 0; i <= MAX; ++ i )
                        {
                              hash[i] 
            = true;
                              path[i] 
            = INF;
                              
            for ( int j = 0; j <= MAX; ++ j )
                              {
                                    g[i][j] 
            = INF;
                              } 
                        }
                        
            for ( int i = 1; i <= N; ++ i )
                        {
                              scanf ( 
            "%d",&K[i] );
                        } 
                        
            for ( int i = 1; i <= N; ++ i )
                        {
                              
            if ( i + K[i] <= N )
                                   g[ i ][ i 
            + K[i] ] = 1
                              
            if ( i - K[i] >= 1 )
                                   g[ i ][ i 
            - K[i] ] = 1
                        }
                        cout 
            << Dijkstra ( A, B ) << endl;
                }
                
            return 0
            }


            SO 代碼:
            #include <iostream>
            using namespace std;
            const int MAX = 200;
            const int INF = 0x7FFFFFF;
            bool UP = true;
            bool DOWN = false;
            int N,A,B;
            int g[MAX+1][MAX+1];
            int hash[MAX+1];
            int path[MAX+1];
            int K[MAX+1];

            int Dijkstra ( int beg , int end )
            {
                path[beg] 
            = 0;
                hash[beg] 
            = false;
                
            while ( beg != end )
                {
                        
            int m = INF, temp;
                        
            for ( int i = 1; i <= N; ++ i )
                        {
                              
            if ( g[beg][i] != INF )
                                   path[i] 
            = min ( path[i], path[beg] + g[beg][i] );
                              
            if ( m > path[i] && hash[i] )
                              {
                                   m 
            = path[i];
                                   temp 
            = i; 
                              }           
                        }
                        beg 
            = temp;
                        
            if ( m == INF )
                             
            break;
                        hash[beg] 
            = false;
                }
                
            if ( path[end] == INF )
                     
            return -1;
                
            return path[end]; 
            }

            bool setGraph ( int n, bool flag )
            {
                 
            if ( flag ) 
                 {
                      
            if ( n + K[n] <= N )
                      {
                           g[ n ][ n 
            + K[n] ] = 1;
                           setGraph ( n 
            + K[n], UP );
                           setGraph ( n 
            + K[n], DOWN );
                      }  
                 }
                 
            else
                 {
                      
            if ( n - K[n] >= 1 )
                      {
                           g[ n  ][ n 
            - K[n] ] = 1;
                           setGraph ( n 
            - K[n], UP );
                           setGraph ( n 
            - K[n], DOWN ); 
                      } 
                 }
                 
            return true;
            }
            int main ()
            {
                
            while ( scanf ( "%d%d%d"&N, &A, &B ) , N )
                {
                        
            for ( int i = 0; i <= MAX; ++ i )
                        {
                              hash[i] 
            = true;
                              path[i] 
            = INF;
                              
            for ( int j = 0; j <= MAX; ++ j )
                              {
                                    g[i][j] 
            = INF;
                              } 
                        }
                        
            for ( int i = 1; i <= N; ++ i )
                        {
                              scanf ( 
            "%d",&K[i] );
                        } 
                        
            for ( int i = 1; i <= N; ++ i )
                        {
                              setGraph ( i, UP );
                              setGraph ( i, DOWN ); 
                        }
                        cout 
            << Dijkstra ( A, B ) << endl;
                }
                
            return 0
            }
            久久久精品2019免费观看| 久久精品国产精品亚洲下载| 人人狠狠综合久久亚洲高清| 日韩亚洲国产综合久久久| 一本色道久久综合亚洲精品| 99久久成人国产精品免费| 99久久夜色精品国产网站| 东方aⅴ免费观看久久av| 四虎国产精品免费久久5151| 日本久久久久久久久久| 国产精品一区二区久久不卡| 久久久中文字幕日本| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 亚洲国产精品嫩草影院久久| 伊人久久综合精品无码AV专区| 免费观看成人久久网免费观看| 亚洲色欲久久久久综合网| 久久久青草久久久青草| 久久99久久99精品免视看动漫| 久久午夜无码鲁丝片| 久久综合伊人77777| 久久久久夜夜夜精品国产| 亚洲欧美日韩久久精品第一区| 性高湖久久久久久久久AAAAA| 77777亚洲午夜久久多喷| 久久无码AV一区二区三区| 久久强奷乱码老熟女网站| 青青草原1769久久免费播放| 国产婷婷成人久久Av免费高清| 亚洲级αV无码毛片久久精品| 久久九九久精品国产| 色综合久久综合网观看| 久久精品国产久精国产思思| 久久久亚洲欧洲日产国码是AV | 成人午夜精品无码区久久| 久久久久黑人强伦姧人妻| 99久久成人18免费网站| 久久精品国产福利国产秒| 26uuu久久五月天| 国产精品99久久久久久www| 色偷偷888欧美精品久久久|