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

    
            

            




            







												


        

            
	

            misschuer
            

            

            


            
	
		

            常用鏈接
            

		

            統計
            
	
		

            積分與排名
            


		
		
            百事通
            
		
				
			
	

		

            最新評論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			旅行商簡化版
		
            
		
             1#include <iostream>
             2#include <cmath>
             3#include <algorithm>
             4using namespace std;
             5
             6struct node
             7{
             8    double x;
             9    double y;
            10}            ; 
            11
            12double dist(node a , node b)
            13{
            14    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
            15}
            16
            17bool comp(node a , node b)
            18{
            19    return a.x < b.x;
            20}
            21
            22double dp[ 1001 ][ 1001 ] , temp;
            23node q[ 1001 ];
            24
            25int main()
            26{    
            27    int n , i , j , k;
            28    dp[ 1 ][ 1 ] = 0; 
            29    
            30    cin >> n;
            31       
            32       for (i = 1 ; i <= n  ; ++ i)
            33           cin >> q[ i ].x >> q[ i ].y;
            34       
            35       sort (q + 1 , q + n + 1 , comp);
            36       
            37       for (i = 2 ; i <= n ; ++ i)
            38           dp[ i ][ 1 ] = dp[i - 1][ 1 ] + dist(q[ i ] , q[i - 1]);
            39             
            40       for (i = 3 ; i <= n ; ++ i)
            41           for (j = 2 ; j < i ; ++ j)
            42           {
            43               if (i == j)
            44               {
            45                   dp[ i ][ j ] = dp[ i ][i - 1] + dist(q[ i ] , q[i - 1]);
            46                   continue;
            47               }
            48               
            49               if (i > j + 1)
            50               {
            51                   dp[ i ][ j ] = dp[i - 1][ j ] + dist(q[ i ] , q[i - 1]);     
            52                   continue;
            53               }
            54               
            55               if (i == j + 1)
            56                   for (k = 1 ; k < j ; ++ k)
            57                   {
            58                       if (k == 1)
            59                       {
            60                           dp[ i ][ j ] =  dp[ j ][ k ] + dist(q[ i ] , q[ k ]);
            61                           continue;
            62                       }
            63                       temp = dp[ j ][ k ] + dist(q[ i ] , q[ k ]);
            64                       if (temp < dp[ i ][ j ])
            65                           dp[ i ][ j ] = temp;
            66                   }
            67           }
            68           dp[ n ][ n ] = dp[ n ][n - 1] + dist(q[n - 1] , q[ n ]);
            69           printf ("%.2f\n" , dp[ n ][ n ]);
            70           return 0;
            71}
            

		
            
			posted on 2009-04-28 18:01 此最相思 閱讀(282) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



久久亚洲精品无码aⅴ大香|
久久精品中文字幕一区|
亚洲级αV无码毛片久久精品|
久久综合偷偷噜噜噜色|
青青草原精品99久久精品66|
久久婷婷国产麻豆91天堂|
久久久国产精品|
久久婷婷五月综合色高清|
国产精品无码久久久久|
久久人妻少妇嫩草AV蜜桃|
久久香蕉国产线看观看乱码|
伊人 久久 精品|
久久免费精品视频|
国产亚洲精久久久久久无码
|
国产精品无码久久综合网|
欧美久久天天综合香蕉伊|
亚洲国产精品无码久久SM|
伊人丁香狠狠色综合久久|
色欲综合久久躁天天躁蜜桃|
国产一区二区三精品久久久无广告|
天天躁日日躁狠狠久久|
国产69精品久久久久观看软件
|
久久精品国产影库免费看|
久久艹国产|
99久久精品免费国产大片|
国产精品99久久精品|
亚洲精品乱码久久久久久蜜桃不卡
|
国产V综合V亚洲欧美久久|
久久久久亚洲AV片无码下载蜜桃|
久久se这里只有精品|
欧美亚洲国产精品久久蜜芽|
久久精品国产亚洲av影院|
国内高清久久久久久|
久久久久久久女国产乱让韩|
青青草原综合久久大伊人导航|
欧美久久综合性欧美|
国产精品免费久久|
色偷偷91久久综合噜噜噜噜|
久久久国产精品|
久久精品国产亚洲AV忘忧草18|
四虎国产精品成人免费久久|