数据结构2019级数据结构大作业

2011级数据结构大作业。

1、公园导游图。

给出一张某公园的导游图，用图的顶点表示各个景点（景点个数大于等于30）；每个景点有属性值（h，t，c ）。其中h表示游览完成这个顶点给游客带来的happiness，t表示游览这个景点需要的时间，c表示游览这个景点需要的费用，顶点之间的边表示路径；边具有属性值w，表示走完这条路径需要的时间。

设计要求】

1 记录游客已经游览过的景点；

2 在某一时刻，指定一个时间t，要求设计一条路径，使得用户可以在t时刻内游览一些景点，获得最大的happiness。要求游客不能多次游览同一个景点；（可以多次通过而不游览）

3 指定一个费用cost，要求设计一条路径，使得用户可以在cost费用范围内游览一些景点，获得最大的happiness。

4 设计一条用户经过所有景点，且不通过某个景点两次（或以上）的游览路径。

2、南京公交线路查询系统

南京公交线路查询系统：

系统提供增加、删除或更改公交线路的功能，可以自行设计合适的数据结构和存储方式。

用户输入要查询的上车站点和目的站点，系统给出换乘路线（换乘路线有多条时，可以给出多个候选。）换乘路线必须说明从哪站上坐哪路车，到哪站下换哪路车，即输入站名s，t后，输出从s到t的某种乘车路线，输出格式为：线路x ：

站名s，…，站名m1 ；换乘线路x ：站名m1，…，站名m2；…；换乘线路x：站名mk，…，站名t。

原始数据：以提供，数据格式如下：

公交线路1 站点1 站点2 。。站点n

公交线路2 站点1 站点2 。。站点n

每一行为一条公交线路，线路名称和站点间以空格隔开。

查询功能要求]

1. 给出最少换乘次数的乘车路线；

2. 给出经过最少站台数的乘车路线；

3. 给出最便宜的乘车线路。

假定每路公交以10站为单位计费，也就是 1元：1-10站；2元：11-20站…….不同路线分开计费。