[藍橋杯][2013年第四屆真題]大臣的旅費（Python描述）

問題 1438: [藍橋杯][2013年第四屆真題]大臣的旅費

時間限制: 1Sec 記憶體限制: 128MB 送出: 835 解決: 212

題目描述

很久以前，T王國空前繁榮。為了更好地管理國家，王國修建了大量的快速路，用于連接配接首都和王國内的各大城市。

為節省經費，T國的大臣們經過思考，制定了一套優秀的修建方案，使得任何一個大城市都能從首都直接或者通過其他大城市間接到達。同時，如果不重複經過大城市，從首都到達每個大城市的方案都是唯一的。

J是T國重要大臣，他巡查于各大城市之間，體察民情。是以，從一個城市馬不停蹄地到另一個城市成了J最常做的事情。他有一個錢袋，用于存放往來城市間的路費。

聰明的J發現，如果不在某個城市停下來修整，在連續行進過程中，他所花的路費與他已走過的距離有關，在走第x千米到第x+1千米這一千米中（x是整數），他花費的路費是x+10這麼多。也就是說走1千米花費11，走2千米要花費23。

J大臣想知道：他從某一個城市出發，中間不休息，到達另一個城市，所有可能花費的路費中最多是多少呢？

輸入

輸入的第一行包含一個整數n，表示包括首都在内的T王國的城市數

城市從1開始依次編号，1号城市為首都。

接下來n-1行，描述T國的高速路（T國的高速路一定是n-1條）

每行三個整數Pi, Qi, Di，表示城市Pi和城市Qi之間有一條高速路，長度為Di千米。

輸出

輸出一個整數，表示大臣J最多花費的路費是多少。

樣例輸入

5

1 2 2

1 3 1

2 4 5

2 5 4

樣例輸出

135

這道題的思考點在于随便找一個點，現在假設找到1這個點，從1這個點出發，找到距離1最遠的點x，然後再從x這個點出發，再找到距離x最遠的點，這個點就是大臣要走的最遠距離。

```python
cnt=0
node=0
def dfs(v,k):   #進行dfs搜尋
    global cnt
    global node
    global vis
    if k>cnt:
        cnt=k
        node=v
    for i in range(len(E[v])):
        if vis[E[v][i][0]]==False: #沒通路過的點都進行一次dfs
            vis[E[v][i][0]]=True #進行标記
            dfs(E[v][i][0],k+E[v][i][1])
            vis[E[v][i][0]]=False #回溯
n=int(input())
E=[[]for i in range(n+1)]
vis=[False for i in range(n+1)]
for i in range(n-1):
    x,y,z=map(int,input().split())
    E[x].append((y,z))
    E[y].append((x,z)) #将各個點進行連接配接，用清單數組的方式進行
vis[1]=True
dfs(1,0)  #找到距離1最遠的點node
vis[1]=False
cnt=0
vis[node]=True
dfs(node,0)  #從node出發，找到最遠的點，就是所要求的最遠距離
res=0
for i in range(1,cnt+1):
    res+=i+10
print(res)