算法|题解

计蒜客 – 奇怪的最短路

凝神长老 · 3月27日 · 2019年 1060次已读

本文写于 2019年03月27日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


我感觉这道题有点难度的,错了很多次。

但是如果把事情说清楚,其实一点难度也没有,就是连续 2 次 BFS。甚至在处理哪些点是合法的这个过程中,都比《逃跑》那题要简单很多,因为没有时间的维度,也不存在间隔 t 循环射击,所以只需要考虑有出边到那些不可达终点的点都是不合法的就可以了。

关键是,不容易想到。

整体的思路是,反向建边(在 insert 边的时候把起点和终点调换),然后从终点开始,BFS 一次,找到哪些点是不能到达终点的,标记下来,然后根据这些标记,判断哪些点是合法的,最后从终点开始反向 BFS,找到的最短路就是答案。

由于是反向建图的,所以所有的操作都是反向 BFS,如果正向判断,就会因为多次遍历所有的点找邻居而超时。

找哪些点是终点可达的时候,扫描一次就可以了,没有必要每个点都扫描。

代码其实很短,就是裸的广搜,没有很复杂的处理过程,下面代码比较长是因为中间加了很多注释,而且有些超时的写法没有删掉。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	private static boolean[] terminalReachablePoints;
	private static boolean[] validPoints;
	private static boolean[] visited;
	private static HashMap<Integer, ArrayList<Integer>> g;
	private static int n;
	private static int s;
	private static int t;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n  = in.nextInt();
		int m = in.nextInt();
		terminalReachablePoints = new boolean[n + 1];
		
		g = new HashMap<>();
		for (int i = 1; i <= n; i++)
			g.put(i, new ArrayList<>());
		for (int i = 0; i < m; i++) {
			int x = in.nextInt();
			int y = in.nextInt();
			g.get(y).add(x);
		}
		s = in.nextInt();
		t = in.nextInt();
		in.close();
		
		//只需要调用一次,计算出所有点的可达性就可以了,没必要每个点都调用一次
		/*
		 * 这会超时 
	private static boolean canPointBeTerminalReachable(int VirtualTerminal) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(t);
		visited[t] = true;
		while (!q.isEmpty()) {
			int current = q.poll();
			if (current == VirtualTerminal) {
				return true;
			} else {
				for (int neighbour : g.get(current)) {
					if (!visited[neighbour]) {
						visited[neighbour] = true;
						q.add(neighbour);
					}
				}
			}
		}
		return false;
	}
		 */
		visited = new boolean[n + 1];
		findTerminalReachablePoints(); // 第 1 次 BFS
		
//		for (int i = 1; i <= n; i++)
//			System.out.println(i + ":" + terminalReachablePoints[i]);
		
		/*
		 * 要弄清楚 "x 可以到达终点 t" 和 "x 是合法的点" 的区别
		 * 
		 * 以下数据就会得到 -1,而事实是 1:
		 * 5 5 4 5 4 3 3 5 3 2 2 1 4 5
		 * 
		 * 下面的代码会把这两点混在一起,只用了一个terminalReachable[i]来表示
		 */
//		for (int i = 1; i <= n; i++) 
//			if (!terminalReachablePoints[i]) 
//				for (int x : g.get(i)) 
//					terminalReachablePoints[x] = false;
		
		// 计算合法的点
		validPoints = new boolean[n + 1];
		for (int i = 1; i <= n; i++)
			validPoints[i] = terminalReachablePoints[i];
		// 默认值直接用是不是可达,不能默认 true/false,否则代码下附的数据,10 号合法性会错
		for (int i = 1; i <= n; i++)
			if (!terminalReachablePoints[i])
				for (int x : g.get(i))
					validPoints[x] = false;
		
//		for (int i = 1; i <= n; i++)
//			System.out.println(i + ":" + validPoints[i]);
		
		visited = new boolean[n + 1];
		int ans = bfs(); // 第 2 次 BFS
		
		System.out.println(ans);
	}

	private static void findTerminalReachablePoints() {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(t);
		visited[t] = true;
		while (!q.isEmpty()) {
			int current = q.poll();
			terminalReachablePoints[current] = true;
			for (int neighbour : g.get(current)) {
				if (!visited[neighbour]) {
					visited[neighbour] = true;
					q.add(neighbour);
				}
			}
		}
	}

	private static int bfs() {
		Queue<Integer> q = new LinkedList<Integer>();
		Queue<Integer> steps = new LinkedList<Integer>();
		q.add(t); // 也是反着来,否则会超时
		steps.add(0);
		visited[s] = true;
		while (!q.isEmpty()) {
			int current = q.poll();
			int step = steps.poll();
			if (current == s) {
				return step;
			} else {
				for (int neighbour : g.get(current)) {
					if (!validPoints[neighbour]) // 合法的点,和能到终点的点不一样
						continue;
					visited[neighbour] = true;
					q.add(neighbour);
					steps.add(step + 1);
				}
			}
		}
		return -1;
	}
	
	// 如果 BFS 从 s 开始找到 t,就不得不遍历所有点,找到给定点的邻居,会超时
	/*
		private static HashSet<Integer> getNeighbours(int current) {
		HashSet<Integer> neighbours = new HashSet<>();
		for (int x = 1; x <= n; x++) 
			if (terminalReachable[x] && !visited[x]) 
//				for (int y : g.keySet()) 
					if (g.get(x).contains(current)) 
						neighbours.add(x);
		return neighbours;
	}
	 */
	

/*
10 15
9 6
6 4
1 7
7 8
8 2
2 3
3 5
9 10
6 10
4 10
4 6
6 8
1 6
7 1
6 2
1 5
这组数据答案是 5
 */
}
0 0 投票
文章评分
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论