<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        




    
	
		


    隨筆 - 147 
文章 - 71 
trackbacks - 0


     
	

    

    
	
		
    
			
    
	
    
		
    <2025年5月>
    
	
    日一二三四五六
    27282930123
    45678910
    11121314151617
    18192021222324
    25262728293031
    1234567
    

    

    
			



			

    常用鏈接
    


    留言簿(1)
    




		
    隨筆分類(146)
    
		
				
			
	
		
    隨筆檔案(147)
    
		
				
			
	
		
    文章分類(28)
    
		
				
			
	
		
    文章檔案(28)
    
		
				
			
	
		
    喜歡的Blog
    
		
				
			
	




    搜索
    

      
	
    • 
		
    •  
	
      • 

    


    最新評論
	
    



    閱讀排行榜
    



    評論排行榜
    


    		
	

    

    
	
					


    
	
	http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
    
【題意簡述】有向圖(互相之間可能不等)中各頂點之間的最短路徑問題。一個人收到消息后便開始向所有他能發送的人（因人以固定的不等時間（長度1~10））發送消息，當所有人都收到消息后的時間長短為評價標準。
    
【分析】Floyd算法。POJ這題的測試數據不嚴密，沒有寫disjoint也可以AC。

    import java.util.*;
    
    import java.io.*;
    

    
    public class poj_1125{
    
    
    
        public static void main(String rgs[]) throws Exception
    
        {
    
        Scanner cin     = new Scanner(new BufferedInputStream(System.in));
    
            int i,j,k,t=0,e,s,n = cin.nextInt();
    
            while(n!=0){
    
                int[][] a=new int[n+1][n+1];
    
                for(i=1;i<=n;i++)
    
                Arrays.fill(a[i],    0xfffff);
    
                for(i=1;i<=n;i++){
    
                t     = cin.nextInt();
    
                    for(j=1;j<=t;j++){
    
                    e     = cin.nextInt();
    
                    s     = cin.nextInt();
    
                    a[i][e]    =s;
    
                }
    
            }                
    
                for(k=1;k<=n;k++){
    
                    for(i=1;i<=n;i++){
    
                        for(j=1;j<=n;j++){
    
                            if(a[i][k]+a[k][j]<a[i][j])
    
                            a[i][j]    =a[i][k]+a[k][j];
    
                    }
    
                }
    
            }        
    
                int min=0xfffff,max;
    
            k    =0;        
    
                for(i=1;i<=n;i++){
    
                max    =0;
    
                    for(j=1;j<=n;j++){
    
                        if(i!=j && a[i][j]>max)
    
                        max    =a[i][j];
    
                }
    
                    if(max<min){
    
                    min    =max;
    
                    k    =i;
    
                }
    
            }
    
                if(k>0)
    
                System.out.println(k    +" "+min);
    
                else
    
                System.out.println(    "disjoint");
    
            n     = cin.nextInt();
    
        }
    
    }
    
}
    

	
    posted on 2009-09-18 10:16 飛翔天使 閱讀(1075) 評論(0)  編輯  收藏  所屬分類: poj 
    

    







    
	    
    




    








    

				
	



    



    







    
        
	



主站蜘蛛池模板：
久热中文字幕在线精品免费|
久久久久久久99精品免费|
大地资源二在线观看免费高清|
亚洲高清国产拍精品26U|
人人玩人人添人人澡免费|
国产精品亚洲片在线|
久久久久久久99精品免费|
久久久久亚洲AV无码麻豆|
免费A级毛片无码A∨免费|
亚洲网红精品大秀在线观看
|
亚洲美女精品视频|
日本阿v免费费视频完整版|
亚洲一区中文字幕|
97无码免费人妻超级碰碰夜夜|
亚洲日本VA午夜在线影院|
国产hs免费高清在线观看|
特级av毛片免费观看|
狠狠亚洲婷婷综合色香五月排名|
国产成人无码区免费内射一片色欲
|
日本免费人成网ww555在线|
亚洲日本一区二区|
99久久免费国产精品特黄|
精品久久久久久亚洲综合网|
亚洲精品国自产拍在线观看|
日本免费人成网ww555在线|
亚洲av乱码一区二区三区|
国产精品免费看香蕉|
日本一区二区三区免费高清在线
|
国产成人人综合亚洲欧美丁香花
|
久久久久久久国产免费看|
亚洲综合久久综合激情久久|
国产精品成人免费视频网站京东|
亚洲第一成年免费网站|
亚洲人成网7777777国产|
8x8×在线永久免费视频|
亚洲成a人片在线观看天堂无码|
亚洲中文字幕视频国产|
最刺激黄a大片免费网站|
精品亚洲国产成人av|
亚洲AV无码国产精品色午友在线|
毛片免费观看的视频在线|