silvercowparty.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 99 行

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


/**
 * ID:3268
 * DIJ
 * @author yhm
 *
 */
public class SilverCowParty {

	static 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();
			int num  =cin.nextInt();
			int x = cin.nextInt()-1;
			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<num;i++){
				int i1= cin.nextInt()-1;
				int i2 = cin.nextInt()-1;
				dis[i1][i2] = cin.nextInt();
			}
			
			int[] low1 =dij(dis, size, x);
			
			
			//转置矩阵
			for(int i=0;i<size;i++){
				for(int j=i;j<size;j++){
					int temp = dis[i][j];
					dis[i][j] = dis[j][i];
					dis[j][i] = temp;
				}
			}
			
			int[] low2 =dij(dis, size, x);
			
			int result = 0;
			for(int i=0;i<size;i++){
				result = Math.max(result, low1[i]+low2[i]);
			}
			System.out.println(result);
		}
		

	}
	
	static int[] dij(int[][] dis, int size, int x){
		int min = MAXNUM,minIndex=x;
		int[] low = new int[size];
		boolean[] inS = new boolean[size];
		for(int i=0;i<size;i++){
			low[i]=dis[x][i];
			inS[i] = false;
		}
		low[x]=0;
		inS[x]=true;
		
		for(int i=0;i<size;i++){
			min = MAXNUM;
			for(int j=0;j<size;j++){
				if(!inS[j]&&low[j]<min){
					min = low[j];
					minIndex = j; 
				}
			}

			inS[minIndex] = true;
			for(int j=0;j<size;j++){
				if(!inS[j]&&dis[minIndex][j]!=MAXNUM&&low[minIndex]!=MAXNUM){
					low[j] = Math.min(low[j], dis[minIndex][j]+low[minIndex]);
				}
			}

		}
		
		return low;
		
	}

}