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

            

            


            
	
		

            常用鏈接
            

		

            統(tǒng)計(jì)
            
	
		

            積分與排名
            


		
		
            百事通
            
		
				
			
	

		

            最新評(píng)論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			旅行商簡(jiǎn)化版
		
            
		
             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 此最相思 閱讀(275) 評(píng)論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            



            


            

	
            
		
		
            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				

            



    
    







            
	   
	



99精品国产在热久久|
国产精品狼人久久久久影院|
久久这里只有精品首页|
伊人久久大香线蕉av不卡|
99精品国产综合久久久久五月天|
久久久久国产精品熟女影院|
91久久精品国产免费直播|
丁香色欲久久久久久综合网|
久久综合狠狠色综合伊人|
97精品依人久久久大香线蕉97|
国产精品视频久久久|
久久综合亚洲色HEZYO社区|
国产69精品久久久久9999|
久久www免费人成看片|
久久精品无码一区二区三区免费|
久久精品国产亚洲av麻豆蜜芽|
精品久久久久一区二区三区|
无码人妻精品一区二区三区久久|
国产亚州精品女人久久久久久
|
久久久精品久久久久久|
国产亚洲精品美女久久久|
久久夜色精品国产噜噜亚洲a|
国产V亚洲V天堂无码久久久|
久久久久久精品成人免费图片|
国产成人99久久亚洲综合精品|
精品国产乱码久久久久久1区2区|
久久人人添人人爽添人人片牛牛|
久久久久亚洲AV成人网人人软件|
99精品国产在热久久无毒不卡|
狠狠色综合网站久久久久久久高清|
久久影院亚洲一区|
久久这里只有精品视频99|
精品久久人人爽天天玩人人妻|
亚洲国产精品久久久久婷婷老年|
久久精品国产亚洲AV大全|
久久er99热精品一区二区|
久久99国产乱子伦精品免费|
国产亚洲精久久久久久无码|
日韩乱码人妻无码中文字幕久久|
精品一二三区久久aaa片|
99精品国产99久久久久久97
|