expensivewedding.java

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

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


/**
 * ID:1062
 * Dij单源最短路径
 * @author yhm
 *
 */
public class ExpensiveWedding {

	static int MAXNUM=Integer.MAX_VALUE;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int M = cin.nextInt();
			int N = cin.nextInt();
			int[][] dis = new int[N+1][N+1];
			for(int i=0;i<=N;i++){
				for(int j=0;j<=N;j++){
					if(i==j){
						dis[i][j]=0;
					}
					else{
						dis[i][j]=MAXNUM;
					}
				}
			}
			int[] degree = new int[N+1];
			for(int i=1;i<=N;i++){
				dis[0][i]=cin.nextInt();
				degree[i]=cin.nextInt();
				int subNum = cin.nextInt();
				for(int j=0;j<subNum;j++){
					int start = cin.nextInt();
					dis[start][i] = cin.nextInt();
				}
			}
			degree[0]=degree[1];
			int min = MAXNUM;
		    for(int i=0;i<=N;i++)
		    {
		    	boolean[] use=new boolean[N+1];
		    	Arrays.fill(use, true);
		        int m=degree[i];
		        int dmax=m;
		        int dmin=m-M;//枚举最大等级,确实等级范围
		        for(int j=0;j<=N;j++)
		        {
		            if(!(Math.abs(dmax-degree[j])<=M&&Math.abs(dmin-degree[j])<=M)){
		            	use[j]=false;
		            }
		        }
		        int t=Dij(dis,use,N+1);
		        if(min>t) min=t;//记录下最优值
		    }
		    System.out.println(min);

			
		}
		


	}
	
	
	
	static int Dij(int[][] dis, boolean[] use, int size){
		int min=0,minIndex=0;
		int[] low = new int[size];
		boolean[] inS = new boolean[size];
		Arrays.fill(inS, false);
		for(int i=0;i<size;i++){
			low[i]=dis[0][i];
		}
		inS[0]=true;
		use[0]=true;
		
		for(int i=1;i<size;i++){
			min = MAXNUM;
			for(int j=1;j<size;j++){
				if(!inS[j]&&use[j]&&low[j]<min){
					min = low[j];
					minIndex = j;
				}
			}
			inS[minIndex]=true;
			for(int j=1;j<size;j++){
				int distance = MAXNUM;
				if(dis[minIndex][j]!=MAXNUM&&low[minIndex]!=MAXNUM){
					distance = dis[minIndex][j]+low[minIndex];
				}
				if(!inS[j] && use[j] && distance<low[j]){
					low[j]=distance;
				}
			}
		}
		
		return low[1];
	}

}