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