实践是检验真理的唯一标准，一个算法最好是通过题目去理解
PAT (Advanced Level) Practice-1003 Emergency (25 分)
题目要求
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
(作为一个城市救援队的领导，你拥有一张特殊的城市地图。这张地图展示了几个零落的由道路连接的城市。每个城市救援队的数量以及两个城市之间的道路长度都被标出。当紧急情况发生时，你的工作就是要决定如何尽快地领导自己的队伍前往事发地点，而且要尽可能多地聚集每个结点的帮手)
Input Specification:
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2
- the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2
and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2
.
Output Specification:
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2
, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input:
1 | 5 6 0 2 |
Sample Output:
1 | 2 4 |
这是一个很典型的搜索问题，通过搜索，获得最短边权和以及最大点权和。
这就引出了我们接下来的算法
–DFS–深度优先搜索
这算法的主要思想是啥呢？
- 首先，我们需要得到一个地图，记录这某些对点之间的距离（当然也有可能记录着每个点的权重)，以及定义一个最短路径当作全局的一种变量（初始值一般是无穷大)。
- 其次，我们需要一个起始点和一个终点，以及一个表，记录某条路是否走过。
- 最后，从起点开始，遍历其他的点，比如我们从0这个城市开始，想去4这个城市，接下来我们看看0->1，那么这个0->1这个路径就要被标记为已经走过，然后又递归进入本函数，一直递归递归，1->2, 2->6……直到递归到起点是我们之前的目的地，那么接下来我们就可以判断了，如果这条路径的总长度小于之前定义的最短路径，那么我们就将最短路径更新为这个新值（因为初始值一般定义为无穷大，所以第一次遍历时一定会更新)，到了最后一步，开始return,一层一层地return，直到回到最初的起点，每一层在获得前一层的return后就要进行下一步，把之前标记为已经走过的道路再重新标记为没走过，这个是很重要的，因为我们的目的不是要标记路走没走过，目的是为了更新最短路径。那么在接下来的搜索中，如果当前的路程已经大于之前更新过的最短路径了，那就啥都憋suo了~，return就完了
针对这个题目，我们可以先看看怎么解
上代码 (ﾉ◕ヮ◕)ﾉ:･*ﾟ✧ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83package 最短路径;
import java.nio.file.Path;
import java.sql.SQLNonTransientConnectionException;
import java.util.Scanner;
public class DFS {
static int n = 0;
static int m = 0;
static int c1 = 0;
static int c2 = 0;
static int[][] map = new int[500][500];
static int[] weight = new int[500];
static boolean[][] visit = new boolean[500][500];
static int totalPath = 0;
static int totalWehght = 0;
static int minPath = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
c1 = scanner.nextInt();
c2 = scanner.nextInt();
for(int i = 0; i < n; i++) {
weight[i] = scanner.nextInt();
}
for(int i = 0; i < m; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
int z = scanner.nextInt();
map[x][y] = map[y][x] = z;
}
dfs(c1, 0, weight[c1]);
System.out.println(totalPath+" "+totalWehght);
}
//这个算法就是整个解题的灵魂
static void dfs(int start, int Lpath, int weights) {
//判断如果到达了终点
if(start == c2) {
if(Lpath < minPath) {
//突然发现这个路径的长度比上一次更新的还短，那就把最短路径的个数更新为1
totalPath = 1;
minPath = Lpath;
totalWehght = weights;
}else if(Lpath == minPath) {
//突然发现最短路径跟上次一样，这两条路径在长度上是等价的，加上这个路径
totalPath++;
if(totalWehght < weights) {
totalWehght = weights;
}
}
return;
}
if(Lpath > minPath) {
//不管你运行到哪个结点了，只要发现你的路径长度比上一次更新过的长，直接就别往下走了
return;
}
for(int i = 0; i < n; i++) {
//从起点（每一次循环的起点，你这次的终点就是下一次的起点）开始遍历其他的没有走过的点，并且起点与该点之间的距离不能为零
if(!visit[start][i] && map[start][i] != 0) {
//先把这个路径设为已经走过了
visit[start][i] = visit[i][start] = true;
//开始递归，把这次的终点当作下次的起点，计算新的路径长度，计算新的点权重和
dfs(i, Lpath + map[start][i], weights + weight[i]);
//上面这个递归结束了，那就把之间的标记给去掉
visit[start][i] = visit[i][start] = false;
}
}
return;
}
}
//相信你通过这个题应该就能大体上看懂了DFS算法了
总结：
- 其实也不是特别难懂
- 算法很精妙
- 时间复杂度应该是O(n^2),还不是特别恐怖。