寻回幼童

小明带来了消息——东区还有三个人，躲在一栋废弃的楼里。他们听到了广播，但不敢出来。

"为啥子不敢？"CC问。

"怕。"小明说，"怕Zero。"

"Zero不在这边。"你说。

"他们不知道。"小明说，"他们躲了三天了，没吃过东西。"

"带我们去找。"CC说。

小明点头。他带着你们穿过三条巷子，绕过两个塌陷点，停在一栋半塌的楼前。

"在里面。"他说，"三楼。"

"你在这等。"你说。

"我不。"小明说，"我要上去。他们怕我，不信你们。"

你看着他——七岁的孩子，眼睛下面有黑眼圈，但眼神很硬。

"好。"你说，"你带路。"

三楼。门是锁的。小明敲门——三长两短，然后喊："是我，小明。我回来了。"

门开了一条缝。一个女人的脸露出来——憔悴，警惕。

"他们是谁？"她问。

"朋友。"小明说，"来接我们的。"

"真的？"

"真的。"你说，"我们有据点，有吃的，有路。你们来，我们一起。"

女人看着你们——六个人，带着武器，但眼神不凶。

"……好。"她说，"我们走。"

她身后还有两个老人，一个腿伤了，一个眼睛不好。CC过去，把腿伤的老人背起来。

"我背。"她说，"你们跟紧。"

下楼。穿过巷子。回到据点。

Echo在据点门口等着。她看到小明，指示灯变成了温暖的黄色——像灯光一样的黄。

"欢迎。"她说。

"你会说话？"小明问。

"会。"Echo说，"我会说话，会算题，会讲故事。你想听哪个？"

"故事。"

"好。"Echo说，"我给你讲一个关于星星的故事。"

题目描述

$n$ 个区域，有些区域之间有通道。从起点出发，访问所有至少有一个躲藏者的区域，然后返回起点。求最短路径。

输入格式

$n, m, s$。然后 $m$ 条边 $(u, v, w)$。然后 $n$ 个整数，表示每个区域是否有躲藏者。

输出格式

最短路径长度。

输入样例

3 2
1 2
2 3

输出样例

6

提示

• 旅行商问题（TSP）或中国邮路问题。
• 小规模用状压DP，大规模用近似算法。
• 注意不是所有区域都需要访问，只访问有躲藏者的区域。

"人齐了？"CC问。

"齐了。"你说，"北区五人，南区四人，东区四人，加上我们六个。十九个人。"

"十九个。"Echo说，"很多了。"

"够吗？"你问。

"够了。"Echo说，"十九个人，一颗心。"

"一颗心？"

"对。"Echo说，"目标一样——活下去，打败Zero。"

"那就干。"CC说。

"等等。"你说，"还有最后一件事。"

"啥子？"

"盟约。"你说，"我们要正式结盟。不是口头，是契约。"

"契约？"

"对。"你说，"每个人签字，承诺不背叛，不抛弃，不放弃。"

"签在哪？"

"这里。"你说，"在据点的石柱上。"

[第十题：缔结盟约]