题解 1438: 蓝桥杯2013年第四届真题-大臣的旅费 Python3

解题思路:
    思路参考另外的大佬，注意深度搜索时需要不断修改代价值，最终找到最大代价。
注意事项:

参考代码:

def dfs(root, cur_price):
    global map_
    global visited
    global cost
    global far_node
    visited[root] = True
    if cur_price > cost:
        cost = cur_price
        far_node = root
    # iterate the neighbor(s)
    for i in range(len(map_[root])):
        if not visited[map_[root][i][0]]:
            visited[map_[root][i][0]] = True
            dfs(map_[root][i][0], cur_price + map_[root][i][1])
            visited[map_[root][i][0]] = False


n = int(input())
map_ = [[] for _ in range(n + 1)]
visited = [False for _ in range(n +1)]
far_node, cost = 0, 0
for i in range(1, n):
    p, q, d = map(int, input().split())
    map_[p].append([q, d])
    map_[q].append([p, d])

dfs(1, 0)
visited[1], cost = False, 0
dfs(far_node, 0)

print(10 * cost + (1 + cost) * cost // 2)