tilthecowscomehome.java

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

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


/**
 * ID:2387
 * DIJ
 * @author yhm
 *
 */
public class TiltheCowsComeHome {

	static int MAXNUM = Integer.MAX_VALUE;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int T = cin.nextInt();
			int size = cin.nextInt();
			int[][] dis = new int[size][size];
			for(int i=0;i<size;i++){
				Arrays.fill(dis[i], MAXNUM);
			}
			for(int i=0;i<T;i++){
				int x = cin.nextInt()-1;
				int y = cin.nextInt()-1;
				int temp = cin.nextInt();
				dis[x][y] = Math.min(dis[x][y], temp); 
				dis[y][x] = dis[x][y];
			}
			Dij(dis,size);
		}

	}
	
	static void Dij(int[][] dis, int size){
		boolean[] inS = new boolean[size];
		int[] low = new int[size];
		int min = MAXNUM;
		int minIndex = 0;
		
		for(int i=0;i<size;i++){
			low[i] = dis[0][i];
			inS[i] = false;
		}
		low[0] = 0;
		inS[0] = true;
		
		for(int i=1;i<size;i++){
			min = MAXNUM;
			for(int j=1;j<size;j++){
				if(!inS[j] && low[j]<min){
					minIndex = j;
					min = low[j];
				}
			}
			
			
			inS[minIndex] = true;
			for(int j=1;j<size;j++){
				int distance = MAXNUM;
				if(low[minIndex]!=MAXNUM && dis[minIndex][j]!=MAXNUM){
					distance = low[minIndex]+dis[minIndex][j];
				}
				if(!inS[j] && distance<low[j]){
					low[j]=distance;
				}
			}
		}
		
		System.out.println(low[size-1]);
	}

}