2020 CCF 大学生计算机系统与程序设计竞赛.pdf

2020 CCF 大学生计算机系统与程序设 计竞赛 CCF CCSP 2020 时间：2020 年 10 月17 日09:00 ∼ 15:00 题目名称 办签证 给他文件系统 垃圾回收器 题目类型 传统型 传统型 传统型 输入 标准输入 标准输入 标准输入 输出 标准输出 标准输出 标准输出 每个测试点时限 1.0 秒 3.0 秒 30.0 秒 内存限制 512 MiB 2 GiB 2 GiB 子任务数目 10 12 20 测试点是否等分 否 否 否 2020 CCF 大学生计算机系统与程序设计竞赛 办签证（Visa ） Visa 办签证（ ） 【题目描述】 世界那么大，我想去看看。 ——顿顿 顿顿想欣赏国外美丽风光，所以他计划前往某国领事馆办理签证。请你为顿顿规划 符合要求的出行路线。 如图 1 所示，顿顿行动范围可以表示为一张有向图G = (V, E)。其中，V 为城市的 集合，E 为城市间民航航班的集合。两个城市间往返方向各最多拥有一个航班，顿顿可 以乘飞机从一个城市前往另一个城市。 V 中包含三种城市：顿顿出发的城市v 、领事馆所在的城市U = {v , . . . , v } ⊂ V 0 1 |U | 和中转城市V − U − {v }。不同城市领事馆办理签证开销各不相同。对于领事馆所在城 0 市v ∈ U ，在该城市办理签证所需开销记为cvisa (v)。 不同航班机票价格各不相同。对于出发城市为 vi 到达城市为 vj 的航班 ei,j = (v , v ) ∈ E ，其机票价格记为c (e )。同时，由于航空管制，各航班有不同的延误概 i j air i,j 率，记为Pdelay (ei,j ) ∈ [0, 1]。 c (v )=8 visa 1 v 1