POJ-1724 Roads + Python （DFS）

POJ-1724 Roads + Python （DFS）

原题链接：1724 -- ROADS

参考资料：王子解救公主力扣 174. 地下城游戏 DFS + Python_xxdragon126的博客-CSDN博客

一 问题描述：

从起始城市1到终止城市N，要求在路费ALL可控的情况下路程最短，返回最短路程。详见原题链接。

解题思路：

## 使用DFS:

# 1 首先，将数据转化为嵌套的字典，以便于查找当前城市所能到达的所有邻接城市，以及到达各邻接城市所需的路程和路费。

# 2 然后，从起始点1开始，查找其邻接点城市，将每个邻接点城市作为初始点，进行dfs搜索

# 2.1 如果子节点（邻接点）已经访问过，则不再访问，返回

# 2.2 如果到达目标城市：

        # 2.2.1 如果当前路费总和不超支：

                # 2.2.1.1 如果当前路程总数更小

                # 2.2.1.2 则更新当前方案及路程数

# 2.3 否则，进行dfs循环，去查找当前节点的子节点

三 代码实现

# POJ-1724 Roads.py
# http://poj.org/problem?id=1724


## 使用DFS:
# 1 首先，将数据转化为嵌套的字典，以便于查找当前城市所能到达的所有城市，以及到达各城市所需的路径和路费
# 2 然后，从起始点1开始，查找其邻接点城市，将每个邻接点城市作为初始点，进行dfs搜索
# 2.1 如果子节点（邻接点）已经访问过，则不再访问，返回
# 2.2 如果到达目标城市：
# 2.2.1 如果当前路费总和不超支：
# 2.2.1.1 如果当前路程总数更小
# 2.2.1.2 则更新当前方案及路程数
# 2.3 否则，进行dfs循环，去查找当前节点的子节点

# 本题跟王子救公主题目的思路比较相似

import collections
import math
## DFS处理
class Solution:
    def DFS(self):
        ###
        start_node = graph[start].keys()
        self.ways = [] # 存储最终方案
        ###
        ## 对每一个节点进行处理
        for node in start_node:
            # 设置初始的总路径
            self.Path = math.inf
            ## 设置访问列表
            ## 将初始节点添加进来
            queue = [start]
            # 父节点为
            pre_node = start
            # 路费之和
            cost_sum = 0
            # 路径之和
            path_sum = 0
            ## 循环
            self.dfs(pre_node,node,queue,cost_sum,path_sum)
        return self.Path

    def dfs(self,pre_node,node,queue,cost_sum,path_sum):
        ## 判断当前节点是否已经访问过
        if node in queue:
            return
        ## 如果未曾访问过则继续
        ## 传递数据
        new_queue = []
        new_queue.append(node)
        for i in queue:
            new_queue.append(i)
        new_queue.append(node)
        new_queue.pop(0)
        ## 判断节点是否为目标点
        if node == target:
            ## 判断有没有超过所需钱数
            if graph[pre_node][node][1] + cost_sum <= ALL:
                ## 判断路径之和是否更小
                if graph[pre_node][node][0] + path_sum < self.Path:
                    # 更新方案
                    self.ways = new_queue
                    self.Path = graph[pre_node][node][0] + path_sum
                    return
        ## 如果没有到达目标节点：则查找当前节点的下一步的节点
        new_nodes = graph[node]
        ### 对每个节点进行分析
        for new_node in new_nodes:
            # 添加入访问列表
            if new_node not in new_queue:
                 self.dfs(node,new_node,new_queue,graph[pre_node][node][1] + cost_sum,graph[pre_node][node][0] + path_sum)
        ## 如果没有可行方案，则返回吧
        return
#####
# 数据转换一下，转成嵌套的索引形式
def sub2graph(grapg):
    dataGrapg = collections.defaultdict(list)
    for key in grapg.keys():
        temp = grapg[key]
        temp_dict = {}
        for i in range(len(temp)):
            temp_dict[temp[i][0]] = temp[i][1:]
            # temp_dict.update()
        dataGrapg[key] = temp_dict
    return dataGrapg

## 迎接数据
ALL = int(input()); #总钱数
N = int(input());# 总城市数
nRode = int(input());# 总路径数

data = []
grapg = collections.defaultdict(list)
for i in range(nRode):
    temp = list(map(int,input().strip().split(' ')))
    grapg[temp[0]].append(temp[1:])
# print(grapg)

## 开始处理
start = 1;# 初始节点
target = N;#目标节点

graph = sub2graph(grapg)#转化为嵌套字典
test = Solution()
ans = test.DFS()
if ans!= math.inf:
    print(ans)
else:
    print('-1')

输入：

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

输出：

11