stockbrokergrapevine.java

PKU中一些数据结构基本算法题的java实现

package PKU.FLOYD;
import java.util.*;


/**
 * ID:1125
 * 全部最短路径的floyd算法
 * @author yhm
 *
 */
public class StockbrokerGrapevine {

	static final int MAXNUM = Integer.MAX_VALUE;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int size = cin.nextInt();
			if(size==0){
				break;
			}
			int[][] dis = new int[size][size];
			for(int i=0;i<size;i++){
				for(int j=0;j<size;j++){
					if(i==j){
						dis[i][j] = 0;
					}
					else{
						dis[i][j] = MAXNUM;
					}
				}
			}
			for(int i=0;i<size;i++){
				int num = cin.nextInt();
				for(int j=0;j<num;j++){
					int end = cin.nextInt()-1;
					dis[i][end] = cin.nextInt();
				}
			}
			
			floyd(dis,size);
		}

	}
	
	static void floyd(int[][] dis, int size){
		int[] maxTime = new int[size];
		
		for(int m=0;m<size;m++){
			for(int x=0;x<size;x++){
				for(int y=0;y<size;y++){
					if(dis[x][m]!=MAXNUM && dis[m][y]!=MAXNUM && x!=y && x!=m && y!=m){
						dis[x][y] = Math.min(dis[x][y], dis[x][m]+dis[m][y]);
					}
				}
			}
		}
		
		for(int i=0;i<size;i++){
			int max = 0;
			for(int j=0;j<size;j++){
				if(max<dis[i][j]){
					max = dis[i][j];
				}
			}
			maxTime[i] = max;
		}
		
		int min = MAXNUM;
		int minIndex = 0;
		for(int i=0;i<size;i++){
			if(min>maxTime[i]){
				min = maxTime[i];
				minIndex = i;
			}
		}
		if(min == MAXNUM){
			System.out.print("disjoint");
			return;
		}
		System.out.print(minIndex+1);
		System.out.println(" " + min);

	}

}