本题转译自 [APIO2009] 抢掠计划。 在遥远的银河系中,有 个空间站,编号为 ,它们之间由 条单向超空间通道相连。 第 个空间站中存储着 TB 的机密数据。 你的登月舰从母舰基地所在的空间站 出发,沿通道飞行,访问各个空间站并下载数据;你可以多次经过同一条通道或同一个空间站,但每个空间站的数据只能下载一次(重复访问不再增加数据量)。 当登月舰到达任意一个指定的数据中转站(共 个)时,可以选择直接结束任务或继续飞行。请计算在最优路径下,登月舰能够下载的机密数据总量的最大值。数据保证可以到达至少一个数据中转站。
输入描述:
第一行包含两个整数 ,分别表示空间站数量和通道数量。 随后一行包含 个整数 ,依次表示各空间站的数据量(单位:TB)。 接下来 行,每行包含两个整数 ,表示存在一条从空间站 指向空间站 的单向通道。 接下来一行包含两个整数 ,其中 是母舰基地所在的起始空间站编号, 是数据中转站数量。 最后一行包含 个互不相同的整数,表示所有数据中转站的编号。


输出描述:
输出一个整数,表示从起点 出发至任意一个中转站时,能够下载的最大机密数据总量(单位:TB)。
示例1

输入

6 7
10 12 8 16 1 5
1 2
2 3
3 5
2 4
4 1
2 6
6 5
1 4
4 3 5 6

输出

47

说明

\hspace{15pt}示例中,登月舰可沿路径 1\to2\to4\to1\to2\to3\to5 访问空间站,下载数据量 10+12+16+8+1=47 TB。
示例2

输入

1 0
100
1 1
1

输出

100

说明

\hspace{15pt}仅有一个空间站,同时也是起点与中转站,下载 100 TB。

备注:
本题已于下方时间节点更新,请注意题解时效性:1. 2025-11-19 优化题面文本与格式。
加载中...