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


	


            
	    
    




            






            

				

            



    
    







            
	   
	



久久se精品一区二区影院|
伊人久久大香线蕉av一区|
国产亚洲精久久久久久无码AV|
精品久久久久久无码人妻蜜桃|
精品伊人久久久|
久久久久久久综合日本亚洲|
欧美日韩久久中文字幕|
国产亚州精品女人久久久久久|
国产成年无码久久久免费|
久久久久亚洲?V成人无码|
久久国产色AV免费观看|
18禁黄久久久AAA片|
久久久久久无码国产精品中文字幕|
亚洲精品国产美女久久久|
久久只有这精品99|
久久久久亚洲av毛片大|
情人伊人久久综合亚洲|
精品久久久久香蕉网|
午夜精品久久久久久毛片|
亚洲欧洲精品成人久久奇米网|
欧美亚洲国产精品久久蜜芽|
久久91精品国产91久久小草|
亚洲国产精品无码久久久蜜芽|
中文字幕精品久久|
亚洲国产成人久久一区久久|
久久99热这里只有精品国产|
国产精品欧美亚洲韩国日本久久|
99久久精品国内|
国产成人精品久久综合|
精品国产婷婷久久久|
久久午夜无码鲁丝片午夜精品|
久久99精品久久久久久秒播|
久久九色综合九色99伊人|
久久久综合香蕉尹人综合网|
亚洲乱码日产精品a级毛片久久
|
人妻无码αv中文字幕久久|
无码八A片人妻少妇久久|
久久久久久久精品成人热色戒
|
久久国产精品一区二区|
久久精品国产99国产精品澳门|
国产精品一区二区久久精品无码
|