b988: NOIP2012 Day2.3.疫情控制
Tags :
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-02-09 18:43

Content

  H国有n个城市,这n个城市用n-1条双向道路相互连通构成一棵树,1号城市是首都,也是树中的根节点。
  H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
  现在,在H国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。
  请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

Input

  第一行一个整数n,表示城市个数。
  接下来的n-1行,每行3个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市u到城市v有一条长为w的道路。数据保证输入的是一棵树,且根节点编号为1。
  接下来一行一个整数m,表示军队个数。
  接下来一行m个整数,每两个整数之间用一个空格隔开,分别表示这m个军队所驻扎的城市的编号。

Output

  共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

Sample Input
4
1 2 1
1 3 2
3 4 3
2
2 2
Sample Output
3
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (10%): 2.0s , <1M
公開 測資點#1 (10%): 2.0s , <1K
公開 測資點#2 (10%): 2.0s , <1K
公開 測資點#3 (10%): 2.0s , <1K
公開 測資點#4 (10%): 2.0s , <1K
公開 測資點#5 (10%): 2.0s , <1M
公開 測資點#6 (10%): 2.0s , <1M
公開 測資點#7 (10%): 2.0s , <1M
公開 測資點#8 (10%): 2.0s , <1M
公開 測資點#9 (10%): 2.0s , <1K
Hint :

  第一支军队在2号点设立检查点,第二支军队从2号点移动到3号点设立检查点,所需时间为3个小时。

  保证军队不会驻扎在首都。
  对于20%的数据,2≤ n≤ 10;
  对于40%的数据,2 ≤n≤50,0<w <105
  对于60%的数据,2 ≤ n≤1000,0<w <106
  对于80%的数据,2 ≤ n≤10,000;
  对于100%的数据,2≤m≤n≤50,000,0<w <109

Tags:
出處:
NOIP2012提高组Day2第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」