HiHoCoder题目链接 1138 Islands Travel

2017/04/01 Algorithm

tips:单元最短路径Dijkstra的实现

HiHoCoder题目链接:

#1138 : Islands Travel

描述

There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3, Y3) …, (XN, YN). You starts at the 1st island (X1, Y1) and your destination is the n-th island (XN, YN). Travelling between i-th and j-th islands will cost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b} denotes the smaller value between a and b) gold coins. You want to know what is the minimum cost to travel from the 1st island to the n-th island.

输入

Line 1: an integer N.</br> Line 2~N+1: each line contains two integers Xi and Yi.</br> For 40% data, N<=1000,0<=Xi,Yi<=100000.</br> For 100% data, N<=100000,0<=Xi,Yi<=1000000000.</br>

输出

Output the minimum cost.

样例输入

3
2 2
1 7
7 6 ### 样例输出
2

分析

构图: 根据题目容易想到使用单源最短路径算法,源点是1st island,任意两个点之间均有一条路径,路径的权值即为两个island的cost,这样构造的图边将会非常稠密,Dijkstra算法会导致TLE。其实对于一个island而言,我们仅仅需要考虑island X方向向左向右最近的两个island,Y方向向上向下最近的两个island一共四个island即可。这样大大减少了所构图的边的数目,然后使用Dijkstra或者SPFA算法即可。

Dijkstra流程:

  1. 初始化:源点的距离初始化为0,其他节点距离初始为正无穷,将源点加入优先队列Q,构造集合S,将源点加入S中

  2. 松弛:从Q中弹出当前距离最小的节点n,把n加入S中,松弛n的邻居的距离,重复该步骤直至Q为空,此时,所有的节点均已加入S

tips: Java中的优先队列不提供更新权值的功能,当一个节点的距离变小的时候我们只能重新加入队列中,每次从队列中弹出一个island的时候,判断该island是够已经加入集合S中,若已经加入直接忽略,如果没有则进行松弛操作。

SPFA流程:

  1. 初始化:源点距离初始化为0,其他节点距离初始化为正无穷,将源点加入FIFO队列Q,构造集合S表示节点是否在FIFO队列中,将源点加入S
  2. 松弛:从FIFO队列中弹出队首节点n,将n从S中删除,松弛n的每个邻居u的距离,松弛后,判断u是否在S中,如果不在,将u加入Q和S,如果在,则不加入。重复该步骤,直至Q为空。

tips:SPFA与Dijkstra非常像,不同之处:1. SPFA使用普通的FIFO队列,Dijkstra使用优先队列 2. SPFA的集合S表示节点是否在队列中,Dijkstra的集合S表示节点的最短距离已经确定 3。Dijkstra是闻名国际的单源最短路径算法,SPFA算法使用的是Bellman的队列优化的思想,在国际上不认可,并且有实验表明SPFA算法运行时间非常不稳定,其他关于SPFA算法请自行Google

源代码

public class Main {
	private static class Island{
		int id;
		int x;
		int y;
		
		public Island(int id,int x,int y){
			this.id = id;
			this.x = x;
			this.y = y;
		}
	}
	
	private static class Pair{ //Pair类用于优先队列中记录当前最短距离
		int id;
		int dis;
		
		public Pair(int id,int dis){
			this.id = id;
			this.dis = dis;
		}
	}
	
	private static int getDistance(int i1,int i2,Island[] islands){
		return Math.min(Math.abs(islands[i1].x - islands[i2].x), Math.abs(islands[i1].y - islands[i2].y));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = null;

		scanner = new Scanner(System.in);
		int N = scanner.nextInt();

		int[] dis = new int[N];
		Island[] islands = new Island[N];
		Island[] islandsXY = new Island[N];
		
		ArrayList<ArrayList<Integer>> neighbors = new ArrayList<ArrayList<Integer>>();		//记录每个节点的邻居
		boolean[] used = new boolean[N];        //集合S
		
		for(int i = 0; i < N; i++){
			int x = scanner.nextInt();
			int y = scanner.nextInt();
			
			islands[i] = new Island(i,x,y);
			islandsXY[i] = new Island(i, x, y);
			
			neighbors.add(new ArrayList<Integer>());
			
			dis[i] = Integer.MAX_VALUE;
		}		
		scanner.close();
		
		Arrays.sort(islandsXY,new Comparator<Island>() {
			public int compare(Island i1,Island i2){
				return i1.x - i2.x;
			}
		}); 
		
		for(int i = 0; i < N; i++){
			if(i + 1 < N){
				neighbors.get(islandsXY[i].id).add(islandsXY[i + 1].id);
			}
			if(i - 1 >= 0){
				neighbors.get(islandsXY[i].id).add(islandsXY[i - 1].id);
			}
		}  //按照X排序,得到X方向邻居
		
		Arrays.sort(islandsXY,new Comparator<Island>() {
			public int compare(Island i1,Island i2){
				return i1.y - i2.y;
			}
		});
		for(int i = 0; i < N; i++){
			if(i + 1 < N){
				neighbors.get(islandsXY[i].id).add(islandsXY[i + 1].id);
			}
			if(i - 1 >= 0){
				neighbors.get(islandsXY[i].id).add(islandsXY[i - 1].id);
			}
		}  //按照Y排序,得到Y方向邻居
		
		//SPFA算法
	//		Queue<Integer> queue = new LinkedList<Integer>(); //FIFO队列
	//		dis[0] = 0;
	//		queue.add(0);
	//		used[0] = true; //集合S
	//		
	//		while(!queue.isEmpty()){
	//			int tmp = queue.poll();			
	//			used[tmp] = false; //不要忘记从集合中删除节点
	//			
	//			ArrayList<Integer> neighbor = neighbors.get(tmp);
	//			for(int j : neighbor){
	//				int distance = getDistance(tmp, j, islands);
	//				if(dis[j] > dis[tmp] + distance){
	//					dis[j] = dis[tmp] + distance;
	//					if(!used[j]){ //不在集合S中,则加入
	//						queue.add(j);
	//						used[j] = true;
	//					}
	//				}
	//			}
	//		}
		
		//Dijkstra算法
		Queue<Pair> queue = new PriorityQueue<Pair>(N,new Comparator<Pair>() {
			public int compare(Pair p1,Pair p2){
				return p1.dis - p2.dis;
			}
		}); //优先队列
		
		dis[0] = 0;
		queue.add(new Pair(0, 0));
		
		while(!queue.isEmpty()){
			Pair pair = queue.poll();
			if(used[pair.id]){
				continue;
			}
			
			used[pair.id] = true;
			
			ArrayList<Integer> neighbor = neighbors.get(pair.id);
			for(int i : neighbor){
				int distance = getDistance(pair.id, i, islands);
				if(dis[i] > dis[pair.id] + distance){
					dis[i] = dis[pair.id] + distance;
					queue.add(new Pair(i,dis[i]));
				}
			}
		}		
		
		System.out.println(dis[N - 1]);		
	}
}

Search

    Table of Contents