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

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku 1797
		
            
		
            2009年7月29日

            題目鏈接：PKU 1797 Heavy Transportation
             
            分類：最短路的變形

            題目分析與算法原型
                     這道題目也是一個最短路徑的變形，就不細講了，Dijkastra中將判斷語句改成dis[j]=Max(dis[j],Min(dis[u],map[u][j]))就OK了

            Code:

             1            #include<stdio.h>
             2#define len 1005
             3#define min -1
             4
             5int map[len][len],dis[len],visit[len],n,m,t;
             6
             7void init()
             8{
             9    int i,j;
            10    for(i=1;i<=n;i++)
            11        for(j=1;j<=n;j++)
            12        {
            13            if(i==j)map[i][j]=0;
            14            else map[i][j]=min;
            15        }
            16}
            17int Min(int a,int b)
            18{
            19    return a < b ? a : b;
            20}
            21void Dijkastra(int s, int v)//s為源點，v為終點（若有的話）
            22{
            23    int i,j;
            24    for(i=1;i<=n;i++)
            25    {
            26        dis[i]=map[s][i];
            27        visit[i]=0;
            28    }
            29    visit[s]=1;
            30    for(i=1;i<n;i++)
            31    {
            32        int max=min,u;
            33        for(j=1;j<=n;j++)
            34            if(visit[j]==0&&dis[j]>max)
            35            {
            36                u=j;
            37                max=dis[j];
            38            }
            39            if(max==min)return;//此語句對于非連通圖是必須的，表示當(dāng)前已經(jīng)不存在路徑了
            40            if(u==v)return ;//若題目是求從給定某個點到另一個給定的點之間的最短路徑時，加上這句節(jié)時
            41            visit[u]=1;
            42            for(j=1;j<=n;j++)
            43                if(visit[j]==0&&map[u][j]!=min)
            44                    if(dis[j]<Min(dis[u],map[u][j]))dis[j]=Min(dis[u],map[u][j]);
            45    }
            46}
            47int main()
            48{
            49    int i,k;
            50    scanf("%d",&t);
            51    for(k=1;k<=t;k++)
            52    {
            53        scanf("%d%d",&n,&m);
            54        init();
            55        for(i=1;i<=m;i++)
            56        {
            57            int a,b,cost;
            58            scanf("%d%d%d",&a,&b,&cost);
            59            map[a][b]=cost;
            60            map[b][a]=cost;
            61            
            62        }
            63        Dijkastra(1,n);
            64        printf("Scenario #%d:\n",k);
            65        printf("%d\n\n",dis[n]);
            66    }
            67    return 0;
            68}
            69
            

		
            
			posted on 2009-07-29 17:42 蝸牛也Coding 閱讀(385) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



精品国产综合区久久久久久|
久久综合久久综合亚洲|
亚洲国产日韩欧美久久|
青草影院天堂男人久久|
久久成人精品视频|
国产精品久久久久乳精品爆|
久久精品国产亚洲精品|
久久综合久久性久99毛片|
伊人久久亚洲综合影院|
久久精品成人欧美大片|
国产激情久久久久影院|
国产激情久久久久影院小草|
国产日产久久高清欧美一区|
久久久久久久尹人综合网亚洲
|
亚洲av伊人久久综合密臀性色|
AV无码久久久久不卡蜜桃|
国内精品久久国产大陆|
国产精品久久一区二区三区|
无码乱码观看精品久久|
色综合久久中文字幕无码|
久久亚洲中文字幕精品有坂深雪|
伊人久久大香线焦综合四虎|
久久久SS麻豆欧美国产日韩|
中文精品久久久久国产网址|
久久九九免费高清视频|
久久综合鬼色88久久精品综合自在自线噜噜|
四虎亚洲国产成人久久精品|
日韩精品久久久肉伦网站
|
香蕉久久夜色精品国产2020|
精产国品久久一二三产区区别
|
国产精品久久波多野结衣|
国产99久久九九精品无码|
亚洲精品久久久www|
久久久久亚洲AV无码永不|
亚洲欧洲精品成人久久奇米网|
亚洲精品无码久久久久久|
一本一道久久精品综合|
97久久国产综合精品女不卡|
精品久久国产一区二区三区香蕉|
久久精品国产亚洲av麻豆蜜芽|
久久成人国产精品二三区|