本文主要是介绍1003 Emergency (25) python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
输入了医疗队的编号和他们之间相连接需要的条数
输出指定的两个医疗队的最短路径的条数，并且在最短路径中能聚集的医疗队的数量
例子：0到2的最短路径可以是0-2.0-1-2.他们都是2的距离，但是0-1-2能聚集1+2+1的医疗队，输出4
用到深度优先算法：尽可能深的搜索，当节点所在的边被探寻过或者不满足条件时，回朔到上一步，反复进行该过程直到所有的点遍历
普适模板：
void dfs(int step):
{if 判断边界条件{}for 尝试每一种可能{if判断满足条件标记继续下一步的dfs恢复初始状态}
}inf = float('inf')
cities_num, roads_num, city_start, city_end = map(int,input().split())
rescue_teams = list(map(int,input().split()))
roads = [[inf for i in range(cities_num)] for i in range(cities_num)] #横纵坐标为两个点，数值为距离
visit = [0 for i in range(cities_num)] #访问节点列表
min_roads = inf #最短路径
min_roads_count = 0 #最短路径条数
max_resue_sum =0 #最大救援队个数for i in range(roads_num):city1, city2, road = map(int,input().split())roads[city1][city2] = roadroads[city2][city1] = roaddef dfs(start, end, road, resue):global min_roads, min_roads_count, max_resue_sum,roads_num,rescue_teams,visitif(start == end):if(road < min_roads): #如果小于当前的road数则更新min_roads_count = 1min_roads = roadmax_resue_sum = resueelif(road == min_roads):#如果等于则更新营救队的最大个数min_roads_count += 1if(max_resue_sum < resue):max_resue_sum = resuereturn 0if(road > min_roads):return 1for i in range(cities_num):if(visit[i] == 0 and roads[start][i] != inf):visit[i] = 1dfs(i, end, road+roads[start][i], resue+rescue_teams[i])visit[i] = 0visit[city_start] = 1
dfs(city_start,city_end,0,rescue_teams[city_start])
print(min_roads_count,max_resue_sum)
这篇关于1003 Emergency (25) python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
