数据结构方面的树形剪枝算法的一个例题,怎么采用C语言的实现的?

Problem Description

Disney's FastPass is a virtual queuing system created by the Walt Disney Company. First introduced in 1999 (thugh the idea of a ride reservation system was first introduced in world fairs), Fast-Pass allows guests to avoid long lines at the attractions on which the system is installed, freeing them to enjoy other attractions during their wait. The service is available at no additional charge to all park guests.
--- wikipedia

Disneyland is a large theme park with plenties of entertainment facilities, also with a large number of tourists. Normally, you need to wait for a long time before geting the chance to enjoy any of the attractions. The FastPass is a system allowing you to pick up FastPass-tickets in some specific position, and use them at the corresponding facility to avoid long lines. With the help of the FastPass System, one can arrange his/her trip more efficiently.
You are given the map of the whole park, and there are some attractions that you are interested in. How to visit all the interested attractions within the shortest time?

Input
The first line contains an integer T(1<=T<=25), indicating the number of test cases.
Each test case contains several lines.
The first line contains three integers N,M,K(1 <= N <= 50; 0 <= M <= N(N - 1)/2; 0 <= K <= 8), indicating the number of locations(starting with 1, and 1 is the only gate of the park where the trip must be started and ended), the number of roads and the number of interested attractions.
The following M lines each contains three integers A,B,D(1 <= A,B <= N; 0 <= D <= 10^4) which means it takes D minutes to travel between location A and location B.
The following K lines each contains several integers Pi, Ti, FTi,Ni, Fi,1, Fi,2 ... Fi,Ni-1, FiNi ,(1 <= Pi,Ni, Fi,j <=N, 0 <= FTi <= Ti <= 10^4), which means the ith interested araction is placed at location Pi and there are Ni locations Fi,1; Fi,2 ... Fi,Ni where you can get the FastPass for the ith attraction. If you come to the ith attraction with its FastPass, you need to wait for only FTi minutes, otherwise you need to wait for Ti minutes.
You can assume that all the locations are connected and there is at most one road between any two locations.
Note that there might be several attrractions at one location.

Output
For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is the minimum time of the trip.

Sample Input
2
4 5 2
1 2 8
2 3 4
3 4 19
4 1 6
2 4 7
2 25 18 1 3
4 12 6 1 3
4 6 2
1 2 5
1 4 4
3 1 1
3 2 1
3 4 1
2 4 10
2 8 3 1 4
4 8 3 1 2

Sample Output
Case #1: 53
Case #2: 14

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构里的剪枝算法的问题运用C语言编程技术的实现的做法
-
多分枝结果的排序和剪枝算法的使用运用,采用C语言的实现
-
关于中国象棋程序里面的阿尔法贝塔剪枝算法的缺点
-
请问一下,搜索对抗算法中AlphaBeta剪枝算法树中的叶子节点的分数是怎么来的?
-
决策树剪枝中,合并子树前后,熵的变化量如何计算?
-
Python进行决策树剪枝提示AttributeError: 'function' object has no attribute 'deepcopy'。
-
这样写minmax算法怎么α-β剪枝
-
求助:(Python)目标检测FPS经剪枝后为什么反而变小?
-
有限制的遍历问题,dijkstra算法是否最简
-
Fibonacci堆中mark域的变换规则和degree域的遵循条件是什么?
-
HDU-1010的剪枝问题的困惑
-
求助!关于棋类AI负极大值AlphaBeta搜索算法问题
-
GBDT中树的大小是固定的吗
-
下面的代码dfs剪枝的if语句是什么意思????
-
CSP20190304代码能过测试用例,逻辑框架没有什么问题,但是为什么一个点都过不了?
-
python算法编码问题咨询
-
求POJ1011stick时间0MS的C++代码
-
ACM菜鸟新手 DP多重背包问题 求大神解答
-
求大神看看这两个代码差别在哪里,运行结果不同啊 poj1014
-
爬虫小程序 - 爬取王者荣耀全皮肤
你也想要王者荣耀全皮肤吗?
动态规划入门到熟悉,看不懂来打我啊
2.1斐波那契系列问题 2.2矩阵系列问题 2.3跳跃系列问题 3.1 01背包 3.2 完全背包 3.3多重背包 3.4 一些变形选讲 2.1斐波那契系列问题 在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n&gt;=2,n∈N*)根据定义,前十项为1, 1, 2, 3, 5, 8, 13, ...
从入门到精通,Java学习路线导航
引言 最近也有很多人来向我"请教",他们大都是一些刚入门的新手,还不了解这个行业,也不知道从何学起,开始的时候非常迷茫,实在是每天回复很多人也很麻烦,所以在这里统一作个回复吧。 Java学习路线 当然,这里我只是说Java学习路线,因为自己就是学Java的,对Java理当很熟悉,对于其它方面,我也不是很了解。 基础阶段 首先是基础阶段,在基础阶段,我们必须掌握Java基础,Mysql数据库,Ora...
如何优雅的爬妹子网
from urllib import request import os from user_agents import ua_list import time import random import re import requests from lxml import etree class MeiziSpider(): def init(self): self.url = ‘https:/...
花了20分钟,给女朋友们写了一个web版群聊程序
参考博客 [1]https://www.byteslounge.com/tutorials/java-ee-html5-websocket-example
对计算机专业来说学历真的重要吗?
我本科学校是渣渣二本,研究生学校是985,现在毕业五年,校招笔试、面试,社招面试参加了两年了,就我个人的经历来说下这个问题。 这篇文章很长,但绝对是精华,相信我,读完以后,你会知道学历不好的解决方案,记得帮我点赞哦。 先说结论,无论赞不赞同,它本质就是这样:对于技术类工作而言,学历五年以内非常重要,但有办法弥补。五年以后,不重要。 目录: 张雪峰讲述的事实 我看到的事实 为什么会这样 ...
Java入门学习路线目录索引(持续更新中)
新增: Redis 入门 【Redis缓存】- 入门——Redis介绍和环境搭建【Redis缓存】- Redis数据结构、基本命令操作、持久化【Redis缓存】- Java客户端Jedis SpringBoot 入门 【SpringBoot 框架】- 入门——环境搭建、工程热部署、idea快捷创建SpringBoot项目【SpringBoot 框架】- SpringBoot 原理分析【S...
一生必看的纪录片
下面按对自己的影响/感悟程度来排序 《人生七年》 概要:人生七年》又称作《56up》也是非常多的网友在看过之后,都让自己陷入了一些思考,对人生思考有一定影响力的纪录片之一导演从1964年开始第一部,在英国找来了不同阶级的十几个七岁的孩子,有男生和女生。有上流社会,也有农场主的儿子等等从七岁开始采访,然后每隔七年就进行一次采访谈话直到现在已经是56岁的时候,在看的时候一定会感慨万千沉思许久,会...
redis——相关问题汇总
什么是redis? Redis 本质上是一个 Key-Value 类型的内存数据库, 整个数据库加载在内存当中进行操作, 定期通过异步操作把数据库数据 flush 到硬盘上进行保存。 因为是纯内存操作, Redis 的性能非常出色, 每秒可以处理超过 10 万次读写操作, 是已知性能 最快的 Key-Value DB。 Redis 的出色之处不仅仅是性能, Redis 最大的魅力是支持保存...
MySQL数据库—SQL汇总
一、准备 下文整理常见SQL语句的用法,使用MySQL5.7测试,参考了尚硅谷MySQL教程及用例。用例sql: 链接: https://pan.baidu.com/s/1tb3-12MRNFjV8drFlN6wzg&amp;shfl=sharepset 密码: fc2h 为了方便查阅可从右侧目录快速索引 二、DQL(Data Query Language)数据查询语言 1、语句顺序 书写顺序...
程序员必须掌握的核心算法有哪些?
由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过...
这应该是把计算机网络五层模型讲的最好是文章了,看不懂你打我
帅地:用心写好每一篇文章! 前言 天各一方的两台计算机是如何通信的呢?在成千上万的计算机中,为什么一台计算机能够准确着寻找到另外一台计算机,并且把数据发送给它呢? 可能很多人都听说过网络通信的 5 层模型,但是可能并不是很清楚为什么需要五层模型,五层模型负责的任务也有可能经常混淆。下面是网络通信的五层模型 说实话,五层模型的具体内容还是极其复杂的,不过今天这篇文章,我将用最简洁的模式,通过网...
HTML CSS整理笔记
常见字体单位: 1.em 移动端常用的字体尺寸单位,说白em就相当于“倍”,比如设置当前的div的字体大小为1.5em,则当前的div的字体大小为:当前div继承的字体大小*1.5。 但当div进行嵌套时,em始终按当前div继承的字体大小来缩放。 2.rem r是root的意思,即相对于根节点html的font-size进行缩放,当有嵌套关系时,嵌套关系的元素的字体大小始终按照根节点的字体大小...
为什么你学不会递归?告别递归,谈谈我的经验
可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了! 可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用,有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话,哪来那么多捷径啊,不过,我还是想写一篇文章,谈谈我的一些经验,或许,能够给你带来一些帮助...
有哪些让程序员受益终生的建议
从业五年多,辗转两个大厂,出过书,创过业,从技术小白成长为基层管理,联合几个业内大牛回答下这个问题,希望能帮到大家,记得帮我点赞哦。 敲黑板!!!读了这篇文章,你将知道如何才能进大厂,如何实现财务自由,如何在工作中游刃有余,这篇文章很长,但绝对是精品,记得帮我点赞哦!!!! 一腔肺腑之言,能看进去多少,就看你自己了!!! 目录: 在校生篇: 为什么要尽量进大厂? 如何选择语言及方...
大学四年自学走来,这些私藏的实用工具/学习网站我贡献出来了
大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意:文中提到的所有资源,文末我都给你整理好了,你们只管拿去,如果觉得不错,转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...
深深的码丨Java NIO 透析
Java 中传统的 IO 包基于流模型实现,交互方式为同步、阻塞,当发生读取或写入操作时,线程会阻塞在此,直到操作完成。编码时采用这种方式虽然源码较直观易维护,但容易产生应用性能下降问题,且 IO 效率及其拓展性存在较大局限 Java 1.4 开始引入 NIO 框架,提供了 Channel(通道)、Selector(IO复用器/选择器)、Buffer(缓冲区),可构建多路复用、同步非阻塞的 IO...
linux系列之常用运维命令整理笔录
本博客记录工作中需要的linux运维命令,大学时候开始接触linux,会一些基本操作,可是都没有整理起来,加上是做开发,不做运维,有些命令忘记了,所以现在整理成博客,当然vi,文件操作等就不介绍了,慢慢积累一些其它拓展的命令,博客不定时更新 free -m 其中:m表示兆,也可以用g,注意都要小写 Men:表示物理内存统计 total:表示物理内存总数(total=used+free) use...
大学四年,我把私藏的自学「学习网站/实用工具」都贡献出来了
在分享之前,先说说初学者如何学习编程,这个话题想必非常的重要,要学好编程,给你一些学习网站也好、实用工具也好,但前提是你知道如何去学习它。 见过很多初学者,以及小鹿我刚开始学习的时候,也是自己瞎摸索,找不到路子,看什么书?看什么资料?编程的方向太多了,如果确定自己的方向?尤其是上大一、大二甚至大三还没有确定自己到底是学习前端还是后天,每天这学一点,那学一块,掌握那么多,没有一门精通的,去面试的时候...
中国麻将:世界上最早的区块链项目
中国麻将:世界上最早的区块链项目 最近区块链这个玩意又被市场搞的很是火热,相信大部分人都不太清楚这玩意到底是怎么样的一个概念,它来了,它来了,它到底是啥~ 国家都开始发文支持了,下面是一个通俗易懂的例子:中国麻将。 甲首先发起一个申请,我要打麻将,组建一个麻将局,这就相当于创建一个区块,这个区块会被广播...
比特币原理详解
一、什么是比特币 比特币是一种电子货币,是一种基于密码学的货币,在2008年11月1日由中本聪发表比特币白皮书,文中提出了一种去中心化的电子记账系统,我们平时的电子现金是银行来记账,因为银行的背后是国家信用。去中心化电子记账系统是参与者共同记账。比特币可以防止主权危机、信用风险。其好处不多做赘述,这一层面介绍的文章很多,本文主要从更深层的技术原理角度进行介绍。 二、问题引入 假设现有4个人...
Python 基础(一):入门必备知识
Python 入门必备知识,你都掌握了吗?
兼职程序员一般可以从什么平台接私活?
这个问题我进行了系统性的总结,以下将进行言简意赅的说明和渠道提供,希望对各位小猿/小媛们有帮助~ 根据我们的经验,程序员兼职主要分为三种:兼职职位众包、项目整包和自由职业者驻场。 所谓的兼职职位众包,指的是需求方这边有自有工程师配合,只需要某个职位的工程师开发某个模块的项目。比如开发一个 app,后端接口有人开发,但是缺少 iOS 前端开发工程师,那么他们就会发布一个职位招聘前端,来配合公司一...
一个老鸟发的公司内部整理的 Android 学习路线图
一个老鸟也发了一份他给公司内部小伙伴整理的路线图,可惜不是MarkDown格式的,而是直接上传的截图,于是我花了些时间,把这位大牛的推荐清单编辑成了Markdown格式,方便大家浏览,学习。这里先放上路线图给大家看看: 有一些链接可能还不是特别准确,因为我只能根据图片上的书或者资源的名字去Google可能的书籍,所以链接上有什么不对的,欢迎大家评论指出,我会及时更正。 ...
Ngrok: 超简单的内网穿透,了解一下 ?
【1】什么是内网穿透? 首先,我们生活中的网络从应用上可以分为内网和外网; 内网就是你自己的网络环境,就你自己能访问,比如你本地测试进行的localhost; 外网就不言而喻了,你看网页,视频等这些网址都是外网。 那么什么又是内网穿透呢?简单的说就是通过访问一个外网地址,然后穿透到你的内网地址。 【2】内网穿透有什么用? 【情景1】 假设你写了一个代码功能,本地测试已经OK,此...
死磕C语言指针
兜兜转转还是逃不过 C 语言,这该死的缘分。 先看一眼我的西野七濑 学习自:https://zhuanlan.zhihu.com/p/89121683 1 指针 1.1 指针是乜嘢 指针(pointer):一个值为内存地址的变量。 char 类型变量的值是字符,int 类型变量的值是整数,指针变量的值是地址。 1.2 指针的声明 数据类型 *指针名,这里的 * 表明声明的变量是...
Python十大装B语法
Python 是一种代表简单思想的语言,其语法相对简单,很容易上手。不过,如果就此小视 Python 语法的精妙和深邃,那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点,并附上详细的实例代码。如能在实战中融会贯通、灵活使用,必将使代码更为精炼、高效,同时也会极大提升代码B格,使之看上去更老练,读起来更优雅。
数据库优化 - SQL优化
前面一篇文章从实例的角度进行数据库优化,通过配置一些参数让数据库性能达到最优。但是一些“不好”的SQL也会导致数据库查询变慢,影响业务流程。本文从SQL角度进行数据库优化,提升SQL运行效率。 判断问题SQL 判断SQL是否有问题时可以通过两个表象进行判断: 系统级别表象 CPU消耗严重 IO等待严重 页面响应时间过长 ...
通俗易懂地给女朋友讲:线程池的内部原理
餐盘在灯光的照耀下格外晶莹洁白,女朋友拿起红酒杯轻轻地抿了一小口,对我说:“经常听你说线程池,到底线程池到底是个什么原理?”
提前送给双十一单身猿们的表白神器
问天下男生,有谁想单身?又有谁想单身一辈子? 虽然本人也是单身狗,但是也是有一个远大的理想,哈哈,大白天的我又开始做梦了 原网址:http://wfhuang.coding.me/LoveJuan/ 在找到一个网页的时候就把它收藏下来了,但是后来觉得不爽,为什么我不能把它抠下来呢?然后想怎么改就怎么改!为所欲为,哈哈!怎么抠下来就不说了,大家应该都知道,如果不知道可以私聊我 再借用https://...
相关热词 c#框架设计 c# 删除数据库 c# 中文文字 图片转 c# 成员属性 接口 c#如何将程序封装 16进制负数转换 c# c#练手项目 c#字段在哪加入 c# 的asp网页倒计时 c# 模拟 鼠标
立即提问