[刷题] 换乘
题目描述（题目来源）
小葱去里约看奥运会，早上从酒店出来后决定坐公交车吗，但是没有直达的路线，只能通过多次换乘公交来达到目的地，现在希望你可以编写一个程序帮助小葱算数到达目的地所需的最少时间。
输入描述
第一行的第一个数字表示终点，起点用数字0表示，第二个数字N表示可选的巴士路线（1≤N≤100）.
第二行开始表示巴士的线路，第一个数字是起点，第二个数字表示这条巴士线路的终点，第三个数字表示这条线路需要的时间
输出描述
输出一行表示最少时间,如果到不了则输出-1。
示例
输入：
6 5
0 2 5
1 4 3
2 6 4
4 6 1
2 4 3
输出：
9
解答思路
这是一个带权有向图，顶点为巴士线路的起点和终点，权重为路线所需时间。
1. 当我看到这个题目时，首先想到的是用深度优先搜索（dfs）来做。从起点出发，沿着每条可能的路线进行搜索，并计算到达位置所需要花费的时间。期间记录一个最小时间，若某条路线到达了终点，且时间较小，则更新最小时间。dfs的实现可以使用递归完成。
让我犹豫的地方是输入数据的保存。如果采用邻接矩阵的方法，需要花费无效的遍历时间，因此我同时用了邻接表和邻接矩阵来表示，邻接表存储每个顶点的邻接顶点，领结矩阵存储权值。（后来想想好像也没必要，单纯用邻接表也不会花费太多的时间）。
邻接表的设计采用一个二维数组route，其中第一维表示顶点，第二维的第一个位置存储该顶点的邻接点数量，后面的位置存储邻接点。
整体的代码实现如下：
1 import java.util.*; 2 3 public class Main { 4 5 private static int ans = Integer.MAX_VALUE; 6 7 public static void main(String[] args) { 8 Scanner in = new Scanner(System.in); 9 int end = in.nextInt(); 10 int N = in.nextInt(); 11 int[][] time = new int[end+1][end+1]; // 邻接矩阵 12 int[][] route = new int[end+1][end+1]; // 邻接表 13 while (in.hasNext()) { 14 int p1 = in.nextInt(), p2 = in.nextInt(), t = in.nextInt(); 15 time[p1][p2] = t; 16 route[p1][0]++; 17 route[p1][route[p1][0]] = p2; 18 } 19 dfs(time, route, 0, 0); 20 System.out.println(ans == Integer.MAX_VALUE ? -1: ans); 21 } 22 23 private static void dfs(int[][] time, int[][] route, int ct, int cp) { 24 if (cp == time.length-1) { 25 if (ct < ans) { 26 ans = ct; 27 } 28 return; 29 } 30 int count = route[cp][0]; 31 for (int i = 1; i <= count; i++) { // 从位置cp开始搜索邻接点 32 int e = route[cp][i]; 33 int t = time[cp][e]; 34 dfs(time, route, ct+t, e); 35 } 36 } 37 }
2. 后来查看讨论区了解到，这个问题其实是“单源最短路径”，即给定带权有向图中的一个顶点（源），求源点到其他各个顶点的最短路径长度。
这个问题的解决方法有Dijkstra算法，它的思路是：
（1）先用一个集合S保存除源点外的其他顶点，其对应的权值有待更新。在邻接矩阵中，用无穷大表示不可达的路径的权值。
（2）从源点出发，从集合S中查找离源点最近的点P1，设权值为W1。此时源点到P的最短路径长度即为W1，因此可以从S中删除P1。
（3）以点P为起点，从集合S中查找P1的邻接点P2，设P1到P2的权值为W2，源点到P2的权值为W3，若W1+W2<W3，则更新W3为W1+W2。（因为此时源点经过P1再到P2的路径会更短）。
（4）重复（2）和（3），直到集合S为空（或者源点到集合S中的最近点的距离为无穷大）。
针对该问题的实现代码如下：
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int end = in.nextInt(); int N = in.nextInt(); int[][] table = new int[end+1][end+1]; for (int i = 0; i <= end; i++) { for (int j = 0; j <= end; j++) { table[i][j] = Integer.MAX_VALUE; } } HashSet<Integer> set = new HashSet<>(); while (N-- > 0) { int p1 = in.nextInt(), p2 = in.nextInt(), t = in.nextInt(); table[p1][p2] = t; set.add(p1); set.add(p2); } set.remove(0); int ans = -1; while (!set.isEmpty()) { Iterator<Integer> it = set.iterator(); // （1）查找离源点最近的点 int node = it.next(); int weight = table[0][node]; while (it.hasNext()) { int n = it.next(); int w = table[0][n]; if (w < weight) { weight = w; node = n; } } // （2）最近的点为无穷大，更新结束 if (weight == Integer.MAX_VALUE) { break; } // （3）到达题目的终点，更新结束 if (node == end) { ans = weight; break; } // （2）查找并更新 it = set.iterator(); while (it.hasNext()) { int n = it.next(); int w = table[node][n]; if (w == Integer.MAX_VALUE) { continue; } if (w + weight < table[0][n]) { table[0][n] = w + weight; } } // （3）删除点 set.remove(node); } System.out.println(ans); } }优质内容筛选与推荐>>
1、just a test
2、【转贴】UCHome二次开发 模板修改
3、eclipse下生成Java类图和时序图，生成UML图
4、-O1 -O2 -O3 优化的原理是什么？
5、Linux：编译安装boost 1.69库