herewegoagain.java

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

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


/**
 * ID:3653
 * DIJ
 * @author yhm
 *
 */
public class HereWeGoAgain {

	static final int length = 2520;
	static int size;
	static int[][] dis;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int Row = cin.nextInt();
			int Col = cin.nextInt();
			if(Col==0 && Row==0) break;
			size = (Col+1)*(Row+1);
			dis = new int[size][size];
			for(int i=0;i<size;i++){
				Arrays.fill(dis[i], Integer.MAX_VALUE);
			}
			for(int i=0;i<Row+1;i++){
				
				for(int j=0;j<Col;j++){
					int v = cin.nextInt();
					String str = cin.next();
					int start = i*(Col+1)+j;
					int end = start+1;
					int time = v==0?Integer.MAX_VALUE:length/v;
					if(str.equals("*")){
						dis[start][end] = time;
						dis[end][start] = dis[start][end]; 
					}
					else if(str.equals(">")){
						dis[start][end] = time;
					}
					else{
						dis[end][start] = time;
					}
				}
				
				if(i==Row) continue;
				
				for(int j=0;j<Col+1;j++){
					int v = cin.nextInt();
					String str = cin.next();
					int start = i*(Col+1)+j;
					int end = start+(Col+1);
					int time = v==0?Integer.MAX_VALUE:length/v;
					if(str.equals("*")){
						dis[start][end] = time;
						dis[end][start] = dis[start][end]; 
					}
					else if(str.equals("v")){
						dis[start][end] = time;
					}
					else{
						dis[end][start] = time;
					}
				}
				
			}
			
			Dij();
			
		}

	}
	
	static void Dij(){
		int[] low = new int[size];
		boolean[] inS = new boolean[size];
		
		for(int i=0;i<size;i++){
			low[i] = dis[0][i];
			inS[i] = false;
		}
		low[0] = 0;
		inS[0] = true;
		
		for(int i=0;i<size;i++){
			int min=Integer.MAX_VALUE;
			int minIndex=-1;
			for(int j=1;j<size;j++){
				if(!inS[j] && low[j]!=Integer.MAX_VALUE && low[j]<min){
					min = low[j];
					minIndex = j;
				}
			}
			
			if(minIndex==-1){
				System.out.println("Holiday");
				return;
			}
			else if(minIndex==size-1){
				System.out.println(min+" blips");
				return;
			}
			
			inS[minIndex]=true;
			for(int j=1;j<size;j++){
				if(!inS[j] && low[minIndex]!=Integer.MAX_VALUE && dis[minIndex][j]!=Integer.MAX_VALUE){
					low[j] = Math.min(low[j], dis[minIndex][j]+low[minIndex]);
				}
			}
		
		}
		
	}

}