1003 Emergency

题目描述：

作为城市的紧急救援团队负责人，你将获得一张你所在国家的特殊地图。
该地图显示了一些通过道路连接的分散城市，道路是双向的。
地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。
当其他城市发出紧急求援信息时，你的工作是尽快带领你的士兵前往该地点，同时，在途中尽可能多地调动救援帮手。

输入格式：
第一行包含四个整数 N，表示城市数量（城市编号从 0 到 N−1），M 表示道路数量，C1 表示你当前所在的城市编号，C2 表示发出紧急求援信息的城市编号。
第二行包含 N 个整数，其中第 i 个整数表示城市 i 的救援队数量。
接下来 M 行，每行包含三个整数 c1,c2,Li，表示城市 c1 和城市 c2 之间存在一条道路相连，道路长度为 Li。
数据保证 C1 和 C2 之间至少存在一条路径相连。

输出格式
共一行，两个整数，第一个整数表示 C1 和 C2 之间最短路的数量，第二个整数表示走最短路的情况下，能聚集到的救援队最大数量。

数据范围
2≤N≤500,
1≤M≤600,
1≤Li≤200,
每个城市包含的救援人员数量不超过 200。

---

题目考点：

dijkstra算法思想

---

题目踩坑：

注意审题：
① 本题要求的是最短路径的数量，并不是求最短路径
② 本题的图是一个无向图，题目中输入只输了一边，所以初始化时另一边也要赋值

---

题目代码：

方法一：(效率不高–测试点5超时)

a_list = input().split(" ")
b_list = list(map(int, input().split(" ")))
# 顶点数
vertex_num = int(a_list[0])
# 边数
edge_num = int(a_list[1])
# 起始点
start = int(a_list[2])
# 终点
end = int(a_list[3])
fmax = float('inf')
# 初始化邻接矩阵
graph = [[fmax for _ in range(vertex_num)] for _ in range(vertex_num)]
# 初始化visit数组 -- 用于在dfs中记录访问过的顶点信息
visit = [0 for _ in range(vertex_num)]
# 存储每条可能的路径
path = []
# 存储最终路径集合
result_path = []
# 创建图
for i in range(edge_num):
    path_list = input().split(" ")
    graph[int(path_list[0])][int(path_list[1])] = int(path_list[2])
    graph[int(path_list[1])][int(path_list[0])] = int(path_list[2])

# 深度遍历找到起始点到终点的所有路径
def dfs(start):
    # 表示start点已经访问过了
    visit[start] = 1
    # 访问过的点放入path列表
    path.append(start)
    # 如果当前访问的点是终点，则加入result_path
    if start == end:
        result_path.append(path[:])
    else:  # 递归遍历
        i = 0
        while i < vertex_num: # 深度遍历
            if visit[i] == 0 and i != start and graph[start][i] < fmax:
                dfs(i)
            i = i + 1
    # 递归完毕后进行逐一清除path中的点，为了下一条路径做准备
    path.remove(path[-1])
    # 将该点重新设置为0，即未访问状态
    visit[start] = 0



teams_max = 0
short_dis_list = []
dfs(start)
# 循环遍历，算出每一个路径的长度
for p in result_path:
    short_dis = 0
    for index in range(len(p)-1):
        short_dis = graph[p[index]][p[index+1]] + short_dis
    short_dis_list.append(short_dis)
# 找到最短路径长度
min_path = min(short_dis_list)
count = 0

for j in range(len(result_path)):
    teams = 0
    if short_dis_list[j] == min_path:  # 算最短路径长度的个数
        count += 1
        for v in result_path[j]:
            teams = teams + b_list[v]
        if teams > teams_max:  # 算最大救援队
            teams_max = teams

print(count, end=" ")
print(teams_max)
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

方法二：（推荐）

n, m, c1, c2 = map(int, input().split())
rescue_num = list(map(int, input().split()))  # 每个城市中救援队的数量
distance = [[float('inf') for i in range(n)] for j in range(n)]  # 城市之间的距离
for i in range(m):
    x, y, z = map(int, input().split())
    distance[x][y] = distance[y][x] = z
 
min_distance_num = [0 for i in range(n)]  # 最短路径数量
max_rescue_num = [0 for i in range(n)]  # 最大救援队数量
max_rescue_num[c1] = rescue_num[c1]
 
# 使用Dijkstra算法求解最短路径
distance_table = [float('inf') for i in range(n)]  # 距离表
distance_table[c1] = 0
is_traversed = [False for i in range(n)]  # 是否已遍历
is_traversed[c1] = True
x = c1  # 设定遍历起点
min_distance_num[c1] = 1
while is_traversed[c2] is False:  # 直到c2被遍历，结束循环
    for i in range(n):  # 遍历x的邻接顶点
        if is_traversed[i] is False and distance[x][i] != float('inf'):  # 顶点可达且邻接顶点未被遍历的情况
            # 将已知直接到i的距离与先到x，再从x到i的距离进行比较
            if distance_table[i] > distance_table[x] + distance[x][i]:  # 如果先到x，再从x到i的距离更近
                min_distance_num[i] = min_distance_num[x]  # 更新最短路径数量
                max_rescue_num[i] = max_rescue_num[x] + rescue_num[i]  # 更新最大救援队数量
                distance_table[i] = distance_table[x] + distance[x][i]  # 更新距离表
            elif distance_table[i] == distance_table[x] + distance[x][i]:  # 如果先到x，再从x到i的距离与已知直接到i的距离相同
                min_distance_num[i] = min_distance_num[i] + min_distance_num[x]  # 更新最短路径数量
                if max_rescue_num[i] < max_rescue_num[x] + rescue_num[i]:  # 如果最大救援队数量小于实际最大救援队数量
                    max_rescue_num[i] = max_rescue_num[x] + rescue_num[i]  # 更新最大救援队数量
    next_data = sorted([distance_table[j] for j in range(n) if is_traversed[j] is False])[0]  # 从距离表中找到出发距离最短的点
    next_index = [j for j in range(n) if distance_table[j] == next_data and is_traversed[j] is False][0]  # 找到该距离最短的点的编号
    is_traversed[next_index] = True  # 标记该点已访问，避免重复访问
    x = next_index  # 更新x点，进入下一轮循环
 
print(min_distance_num[c2], max_rescue_num[c2])
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

---

收获：

本题的最大收获是了解了dijkstra算法的思想，学会了找到源点到各个顶点的最短路径以及源点到目标点的所有路径。
本题是在dijkstra算法上的变形；正常的dijkstra算法是求出源点到各个点的距离存入到dist数组以及求出源点到各点的路径，存入path数组；
本题也采用dijkstra算法的思想，只是在遍历时，要判断最大营救队的数量以及最短路径的数量