信息学奥赛一本通T1498-Roadblocks(最短路径算法Dijkstra)

解题思路:思路在代码中,很清晰的.

注意事项:求的是农场 1到农场 4的第二短的路径(路径里一定要有农场 1和农场 4).

参考代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 键盘录入.
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int R = scanner.nextInt();
		// 存储点和权值的集合.
		ArrayList<lx1_2> list[] = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			// 初始化集合list[i],不然后面会报错.
			list[i] = new ArrayList<lx1_2>();
		}
		for (int i = 0; i < R; i++) {
			// 将数据存储到集合list中,方便计算.
			addlx1_2(list, scanner.nextInt() - 1, scanner.nextInt() - 1, scanner.nextInt());
		}
		// 输出次最小路径.
		System.out.println(SubminimalSpanningTree(list, N));
	}

	// 存储点和边的权值.
	static void addlx1_2(ArrayList<lx1_2> list[], int id1, int id2, int weight) {
		list[id1].add(new lx1_2(id2, weight));
		list[id2].add(new lx1_2(id1, weight));
	}

	// 生成严格次最小路径.
	static int SubminimalSpanningTree(ArrayList<lx1_2> list[], int n) {
		// 赋一个大的值(因为找的是小值).
		int INF = Integer.MAX_VALUE;
		// 最小路径存储(通过while最后得到最优的最小路径).
		int MinimumPath[] = new int[n];
		// 次最小路径存储(通过while最后得到最优的次最小路径).
		int Secondaryminimumpath[] = new int[n];
		// 为数组MinimumPath和数组Secondaryminimumpath,初始化为INF.
		Arrays.fill(MinimumPath, INF);
		Arrays.fill(Secondaryminimumpath, INF);
		// 利用PriorityQueue(优先队列)实现由从小到大的权值排列的集合,从而得出最优解.
		PriorityQueue<lx1_2> queue = new PriorityQueue<lx1_2>();
		// 加入队列第一个元素.
		queue.add(new lx1_2(0, 0));
		// 当优先队列为空的时,即得出最优解循环结束.
		while (!queue.isEmpty()) {
			// poll()函数取出队列中第一个元素并删除.
			lx1_2 qLx1_2 = queue.poll();
			// 遍历出和qLx1_2.id连接的点,寻找最优解.
			for (lx1_2 lx : list[qLx1_2.id]) {
				// qLx1_2.weight是之前边权值的总和,lx.weight是qLx1_2.id连接的点的边权值.
				int Weightsand = lx.weight + qLx1_2.weight;
				// Weightsand与MinimumPath[lx.id]相比较,如果小则赋值给MinimumPath[lx.id],最后的结果是MinimumPath[lx.id]成为到lx.id这个点的最小总权值.
				if (Weightsand < MinimumPath[lx.id]) {
					// 这个导致Secondaryminimumpath[lx.id]永远比MinimumPath[lx.id]慢一步,会让严格次最小路径得出.
					Secondaryminimumpath[lx.id] = MinimumPath[lx.id];
					// MinimumPath[lx.id]获得新的最优值.
					MinimumPath[lx.id] = Weightsand;
					// 将新的最优值放入队列,让数组Secondaryminimumpath逐渐优化,使严格次最小路径得出.
					queue.add(new lx1_2(lx.id, Weightsand));
					// 有可能权值和大于最小权值和而小于次小权值和,所以要更新集合Secondaryminimumpath.
				} else if (Weightsand > MinimumPath[lx.id] && Weightsand < Secondaryminimumpath[lx.id]) {
					Secondaryminimumpath[lx.id] = Weightsand;
					// 将新的最优数放入队列,让严格次最小路径得出.(因为怕这条路上有更优的,所以一定要加这一步).
					queue.add(new lx1_2(lx.id, Weightsand));
				}
			}

		}
		// 返回最后到达点的次最小权值.
		return Secondaryminimumpath[n - 1];
	}
}

//类lx1_2是用来存储键盘录入数据的,是辅助list[i] = new ArrayList<lx1_2>();来存储数据的.
//如果键盘录入 1 2 3 ,那么类lx1_2用来存储2和3.
class lx1_2 implements Comparable<lx1_2> {
	int id;
	int weight;

	public lx1_2(int id, int weight) {
		super();
		this.id = id;
		this.weight = weight;
	}

	// compareTo(Node p)是Comparable<Node>接口的实现方法,用来规定PriorityQueue(优先队列)的排列顺序
	@Override
	public int compareTo(lx1_2 o) {
		// TODO 自动生成的方法存根
		// 这个是从小到大的排序方式.
		return Integer.compare(weight, o.weight);
	}

}