题目描述(图论)
很久以前，某王国拥有 n 个大城市，为了方便交通，国王下令修建了大量的用于连接首都和其他各大城市高速路。
为节省经费，王国采用了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。并且，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
G商队是王国重要的运输商队，他们奔波于各大城市之间，为王国的人们运输商品，实现长途贸易。所以，从一个城市马不停蹄地到另一个城市成了G商队最常做的事情。他们有一个钱袋，用于存放往来城市间的运输费。
在运输过程中G商队发现，如果不在某个城市停下来休整，在连续行进过程中，他们所花的运输费与他们已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他们花费的运输费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
G商队想知道：他们从某一个城市出发，如果中间不休息，到达另一个城市，所有可能花费的运输费中最多是多少呢？
输入
输入的第一行包含一个整数n，表示包括首都在内的王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述王国的高速路（王国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。输入城市数（〈10），长度（〈=100）
输出
输出一个整数，表示G商队最多花费的运输费是多少。
样例输入
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出
135
破题思路
主要涉及的函数：根据图的遍历，不断更新点到点之间的距离的递归函数update（），根据距离计算花费的函数。
其它设置：初始化一个全为0的图的邻接矩阵变量，将其设置为全局变量，方便实时共享改变的邻接矩阵变量。
程序源码
n = int(raw_input())
#如果n=5,则有dis=[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
dis = [[0 for _ in range(n)] for _ in range(n)]
def update(s,a,v):
#定义全局变量dis
global dis
dis[s][a] = v
dis[a][s] = v
#print dis
#确定待更新的矩阵元素位置，存入update_list
update_list = [i for i in range(n) if (dis[s][i] != 0 and i!= a)]
if(len(update_list)):
for i in update_list:
#比较s到i和i到a的距离，如果dis[a][s]+dis[s][i])<dis[i][a]，则说明s为直线ai之间的一个点；如果dis[i][a] == 0，则说明a和i之间没有直达的路。两种情况都需要更新i和a点之间的距离。
if((v+dis[s][i])<dis[i][a] or dis[i][a] == 0):
update(i,a,v+dis[s][i])
else:
return
edge_list=[]
for _ in range(n-1):
s,a,v = map(int, raw_input().split())
edge_list.append((s,a,v))
dis[s-1][a-1] = v
for s,a,v in edge_list:
update(s-1,a-1,v)
update(a-1,s-1,v)
#print dis
#map先取每列的最大值，再取每列最大值的最大值
max_length = max(map(max,dis))
#max_length*10+（1+2+...+max_length）
print max_length*10+(max_length+1)*max_length/2