存在与否

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 exists.in 输出文件 exists.out

【问题描述

当前,随着经济的深入变革,我们的社会环境也得到了很大改善,在中国,城市人口每年以7%的速度增长,一些大城市的人口增长速度更是快的惊人,一个显而易见的例子是:今天的上海每小时新增加10所住宅和100平方米的公路,已率先成为世界大都市。
由于人口和城市面积的急剧增长,公共交通成为一个重要的问题,于是大量的十字路口遍步整个城市。
举个例子,以前广州海珠区有N个自然村,有一些道路把这些村子连接起来,使得任意两个村子都存在一条路径相通,任意两条路只在某个村子那里相交。简单来说,海珠区可以被视为一棵树,村子是结点,路为边,海珠区政府就位于树的根结点所在的村子。这棵树有M个叶子结点(L[1],...,L[M],换言之,这M个村子中的每一个都只与一个村子直接相连),其它(N-M)个结点(包括根结点)每一个结点都至少有两个子结点,如下图1所示。
近年来,又新建了一条环状交叉路穿过了这M个村子(L[1],...,L[M]),如图2所示:

图1                                                            图2
假定L[0]是一个离海珠区很远的邮局,但也在环路上。邮递员想以尽可能快的速度往各个村子送EMS,从统计数据中你可得知邮递员走每条路需花费的时间,现在邮局局长想知道是否存在一个环(L[0]→L[1]→...→L[M]→L[0]),使得邮递员只需访问这N个村子中的每个村子一次,如果可行,输出完成这个任务所花费的最小时间,否则只需输出“-1”(双引号不需输出)。
【输入格式】
输入数据有两部分组成:
第一部分的第一行是一个正整数N(3≤N≤1000),表示村子的个数,接下来有N-1行,第i行有三个正整数Xi(1≤Xi≤N),Yi(1≤Yi≤N),Ti(0< Ti≤1000),用来描述第i条边,其中Yi为树中Xi的父结点,Ti表示从Xi到Yi或者从Yi到Xi所需的时间。
第二部分的第一行是一个正整数M(1≤M< N),表示叶子结点的个数,接下来有M+1行,表示交叉路,第i(0≤i≤M)行有三个非负整数L[i](0≤L[i]≤N),L[i+1](0≤L[i+1]≤N),Ci(0< Ci≤1000),假定L[0]=L[M+1]=0,交叉路是一个环L[0]→L[1]→L[2]→...→L[M]→L[M+1],Ci表示从L[i]到L[i+1]或者从L[i+1]到L[i]所需的时间。
【输出格式】

输出只有一个整数,如果存在一个满足上述要求的环,输出从邮局出发遍历所有村子并返回邮局所需的最小时间,否则输出“-1”(不包括双引号),输出不需要多余的空格。

【输入样例】
输入文件名:exists.in
3
2 1 1
3 1 1
2
0 2 1
2 3 1
3 0 1
输出文件名:exists.out
4
提示:可行的环为0→2→1→3→0,总的时间为4,如下图: