隨筆 - 147 
文章 - 71 
trackbacks - 0


           
	

          

          
	
		
          
			
          
	
          
		
          <2025年7月>
          
	
          日一二三四五六
          293012345
          6789101112
          13141516171819
          20212223242526
          272829303112
          3456789
          

          

          
			



			

          常用鏈接
          


          留言簿(1)
          




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




          搜索
          

            
	
          • 
		
          •  
	
            • 

          


          最新評(píng)論
	
          



          閱讀排行榜
          



          評(píng)論排行榜
          


          		
	

          

          
	
					


          
	
	http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
          
【題意簡(jiǎn)述】有向圖(互相之間可能不等)中各頂點(diǎn)之間的最短路徑問題。一個(gè)人收到消息后便開始向所有他能發(fā)送的人（因人以固定的不等時(shí)間（長(zhǎng)度1~10））發(fā)送消息，當(dāng)所有人都收到消息后的時(shí)間長(zhǎng)短為評(píng)價(jià)標(biāo)準(zhǔn)。
          
【分析】Floyd算法。POJ這題的測(cè)試數(shù)據(jù)不嚴(yán)密，沒有寫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 飛翔天使 閱讀(1079) 評(píng)論(0)  編輯  收藏  所屬分類: poj 
          

          







          
	    
    




          








          

				
	



          



    







          
        
	




主站蜘蛛池模板：
阿图什市|
乌审旗|
柘城县|
枞阳县|
武城县|
新丰县|
石渠县|
化德县|
廊坊市|
蓝山县|
惠州市|
祁门县|
涿鹿县|
彩票|
罗甸县|
英德市|
邹城市|
仪征市|
手游|
嘉禾县|
忻州市|
乌鲁木齐县|
泸溪县|
大庆市|
潞西市|
扬州市|
安乡县|
咸阳市|
新河县|
漳平市|
射洪县|
天峻县|
乌兰察布市|
毕节市|
安西县|
武清区|
固原市|
山东|
于田县|
治多县|
上林县|