• <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)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



国产精品VIDEOSSEX久久发布
|
国产精品久久久久影视不卡|
亚洲va久久久噜噜噜久久狠狠|
午夜人妻久久久久久久久|
国产精品视频久久久|
久久久久久久久66精品片|
精品无码久久久久久午夜|
久久久受www免费人成|
久久精品中文闷骚内射|
欧美精品福利视频一区二区三区久久久精品
|
国内精品久久久久影院薰衣草|
97久久精品人妻人人搡人人玩|
精品无码久久久久久国产|
久久精品国产亚洲AV无码娇色
|
久久精品国产亚洲一区二区|
伊人久久大香线蕉无码麻豆|
久久久久久久97|
99久久做夜夜爱天天做精品|
亚洲国产精品久久久久婷婷软件|
日韩欧美亚洲综合久久|
免费一级欧美大片久久网
|
久久福利资源国产精品999|
国产免费久久精品丫丫|
999久久久无码国产精品|
亚洲精品乱码久久久久久按摩
|
日韩va亚洲va欧美va久久|
91麻精品国产91久久久久|
国产午夜精品久久久久免费视
|
国产精品久久久久国产A级|
狠狠色综合网站久久久久久久高清
|
免费观看久久精彩视频|
精品乱码久久久久久久|
久久久久久久亚洲Av无码|
久久男人Av资源网站无码软件|
久久免费看黄a级毛片|
尹人香蕉久久99天天拍|
伊人久久精品影院|
久久人做人爽一区二区三区|
久久久久久精品免费看SSS|
久久婷婷五月综合国产尤物app
|
久久精品国产欧美日韩|