问题 3559 --城墙

3559: 城墙

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

有一个国家,城市之间都用城墙连接起来,每个城市里有一个或者没有打高尔夫的高手。现在这些高尔夫高手打算挑一个空地r一决高下(空地就是由城墙围起来的地方)。由于国家管制,所属i城市的人不能去其他任意的城市。因此有些人要去空地r不得不翻越一些城墙,当然翻墙是件很困难的事情,所以尽量能少翻墙。现在问你挑哪个区域来做为他们比赛的地点,使得他们翻过墙的总和最小。


Figure1:输入样例情况图
Figure2:翻越城墙数最小的一种情况

输入

第一行:M 表示空地数(2 <= M <= 200)
第二行:N 表示城市数目(3 <= N <= 250)
第三行:L 表示高尔夫高手人数(1 <= L <= 30)
第四行:L个数字,依次表示L位高尔夫高手所在城市编号
接下来2*M行:每两行对应一个空地,第一行表示空地周围的城市数,第二行表示城市的代号,前M-1个按城市编号按顺时针顺序输出,第M个按逆时针输出。

输出

输出一个整数:总共需要翻越的城墙数的最小值

样例输入

10
10
3
3 6 9 
3
1 2 3 
3
1 3 7 
4
2 4 7 3 
3
4 6 7 
3
4 8 6 
3
6 8 7 
3
4 5 8 
4
7 8 10 9 
3
5 10 8 
7
7 9 10 5 4 2 1

样例输出

2

来源

 

[提交][状态]