Disney's FastPass

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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
HDU4114-floyd+ 状压dp
Disney's FastPass Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2406    Accepted Submission(s): 661 Problem Description Disne
HDU Disney's FastPass
原创:http://acm.hdu.edu.cn/showproblem.php?pid=4114 题意:从1开始遍历完k个给定点,最终回到1,的最少时间 思路:首先是floyd预处理出任意两点之间的最短距离。dp[state1][state2][u]表示在该状态state1(已经访问过的景点)、state2(手中有的景点的票)、目前所在的位置时所花费的时间的最小值,于是答案就是dp[(1
hdu 4114 Disney's FastPass
题意:游戏园里有N个区域,有M条边连接这N个区域,有K个要访问的景点。对于每个景点告诉你这个景点所在的区域,要访问这个景点需要等待一定时间,如果没有FastPass,等待时间有Ti,否则等待时间为FTi,接下来的Ni,表示有Ni个区域可以得到这个景点的FastPass,问从区域1出发,再回到区域1所需要的最少时间。 状态压缩,dis[i][s1][s2],表示当前走到这个点,s1表示拿到了哪些景
hdu Disney's FastPass(状态压缩dp)
这种题我一直喜欢用bfs搞的,但是这个题不太好bfs,主要是我刚开始想的是通过边进行状态转移,这样很不好写。。。于是就坑爹了,调了很久sample都没出。。。 于是学习了一下别人的思想。。。通过“目的”来进行状态转移而不是边。当你在某个点的时候,你可以为了游历某个景点去某个点,也可以为了获取某个点的票而去某个点。能想到这一点的话状态转移方程就很好写了,但是也要能想到啊。。。 ps:注意代码中的
HDU Disney's FastPass(状态压缩DP)
题目链接:点击打开链接 题意:给你一个n个点的完全图, 图中任意两个点都有直接相连的路,在某些点上可以获得某些景观的入场券,有入场券和没有入场券进入景观要等候的时间不同,有k个景观,要求从1点出发参观完所有景观后回到1的最小花费。 思路: 很明显的状态压缩DP, 因为 k 很小,所以可以压缩成一个整数,表示哪些景观已经参观完了。 然后还要表示出当前到了哪个点, 又因为有没有票的等候时间是不同的
hdu 4114 Disney's FastPass 状压dp+floyd
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
HDU 4114 Disney's FastPass(状压dp)
题意就是给你一些点,有的地方有景区,有的地方有某些景点的优先票,拿优先票去景点和不拿的时间不一样。问从地点1出发去所有景点再回来的最短时间。 得把景点,景区进行状压。即dp[i][j][k]代表参观景点状态为i,景区状态为j,停在k的最短时间。 先floyd一下处理出最短路。 对于一种状态i,j,为了保证dp[i][j][k]在递推的时候是最短时间可以先用2个(1-n)for循环进行更新,因
Hdu 4114 Disney's FastPass(状压dp)
题目链接
hdu 4114 Disney's FastPass 状压dp
点击打开链接 题意: 游戏园里有N个区域,有M条边连接这N个区域,有K个要访问的景点。对于每个景点告诉你这个景点所在的区域,要访问这个景点需要等待一定时间,如果没有FastPass,等待时间有Ti,否则等待时间为FTi,接下来的Ni,表示有Ni个区域可以得到这个景点的FastPass,问从区域1出发,再回到区域1所需要的最少时间。 思路: 状态压缩,dis[i][s1][s
HDU 4114 Disney's FastPass(floyd+状态压缩DP)
Disney's FastPass Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2419    Accepted Submission(s): 670 Problem Description Disne
disney BRDF代码解释
图片稍后补上..vec3 BRDF( vec3 L, vec3 V, vec3 N, vec3 X, vec3 Y ) { //计算有用的变量 float NdotL = dot(N,L); float NdotV = dot(N,V); //简单的背面判断 if (NdotL < 0 || NdotV < 0) return vec3(0);vec3 H = norma
DisneySprings - 迪士尼之泉
DisneySprings - 迪士尼之泉 https://disneyworld.disney.go.com/ https://disneyworld.disney.go.com/destinations/disney-springs/ 迪士尼之泉    
基于物理的渲染—迪士尼的渲染模型
今天给大家介绍的是一篇关于基于物理渲染(Physically Based Rendering)的技术论文。PBR是最近游戏渲染领域中比较高级的渲染管线。相比于传统基于Lambert以及Phong模型的渲染管线,PBR采用更加真实的材质模型,能够更好地表现物体表面不同粗糙度带来的不同反射效果,从而能够更贴近真实地模拟各种不同的材质。采用PBR的材质能更好地模拟金属、非金属以及不同粗糙度等材质对光的反射效果。我们推荐这篇论文,希望对PBR渲染管线原理有兴趣的开发者,能够通过此文加深对PBR的理解,从而能够在项目
Physically-Based Shading at Disney节选翻译
Physically-Based Shading at Disney节选翻译 图片稍后补上 1 Introduction 2 The microfacet model3 Visualizing measured BRDFs 3.1 The “MERL 100” 3.2 BRDF Explorer 3.3 Image slice4 Observations from MERL materi
基于物理着色(三)- Disney和UE4的实现
基于物理着色(三)- Disney和UE4的实现 文刀秋二 · 3 个月前 前两篇文章(基于物理着色(一),基于物理着色(二)- Microfacet材质和多层材质)已经介绍了模拟大部分材质的计算模型。这一节会则是谈谈Disney的Principled BRDF和UE4(UE4的材质系统是Disney的简化版)是如何用这些计算模型设计出一个直观,好用,能让Artists快速迭代出各
hdu4114.Disney's FastPass
http://acm.hdu.edu.cn/showproblem.php?pid=4114 题意:给定一个带权无向同( 思路,状态压缩dp,f[i][j][mark]表示当前在j这个点,已经‘游’过的点的2进制状态为i,手上有fastpass的2进制为mark的最少时间 则f[i][j][mark] => f[i | (1 同理f[i][j][mark] => f[i][j'][ne
基于物理的渲染-Disney Shading
Physically Based Shading at Disney 1 介绍 在我们成功地完成了基于物理的头发明暗处理(Tangled .27)之后,我们开始考虑开发基于物理模型的更广泛的阴影处理模型。在基于物理的头发模型中,我们能够在保持美术控制的同时获得很大程度的视觉丰富性。然而,事实证明,将头发的光照与场景的其余部分结合在一起,仍然使用传统的“ad-hoc”阴影模型和实时的灯光是很有挑战性...
matlaB直接画出disney的MACD曲线
<br />load disney.mat<br />dis_CloseMACD = macd(dis); <br />dis_OpenMACD = macd(dis, 'OPEN');<br />plot(dis_CloseMACD); <br />plot(dis_OpenMACD); <br />title('MACD for Disney')
disney brdf viwer
disney brdf viwer 可视化
[sig12][pbs]迪斯尼的physically based lighting
http://blog.selfshadow.com/publications/s2012-shading-course/burley/s2012_pbs_disney_brdf_slides_v2.pdfhttp://blog.selfshadow.com/publications/s2012-shading-course/burley/s2012_pbs_disney_brdf_notes.p
GYM 100685 J【交互题】
俄罗斯的人经常出一些交互题,比如强制离线之类的题目 这题是二分+交互 对于每一盏灯ii,我们假设前面的灯位置都排好了位置,那么就二分那些这一盏灯所在的位置,询问的次数是nlog(n)nlog(n)次。 另外如果死循环的话,那就是没有方案,设置一个cnt上限来判断死循环。// whn6325689 // Mr.Phoebe // http://blog.csdn.n
disney (map模拟)
A new machine was introduced into disney world. Every day, there is a long queue because of its function. Everyone can input their score or update their score. If you want to know the maximum or the a
Disney
Disney
s2012_pbs_disney_brdf_slides_v2
s2012_pbs_disney_brdf_slides_v2
BRDF 材质贴图
Segment 0 关键词 BRDF 材质,一种材质纹理,用来贴反射光的。 PBS physical based shading, 基于物理成像算法。 microfacet model,一种表面模型,是diffuse加上反射,反射一般由微表面分布函数D,反射系数函数F,自遮挡G组成。请注意这个模型是对每一个pixel都成立的。 uv的界限。在Unity里面,也不知道是我操作不好还是怎样,一旦UV在0
Gym 100685J Just Another Disney Problem(交互/排序)
题目地址:http://codeforces.com/gym/100685/problem/J 思路:由最多询问次数10000次和n最大为1000,排序的时间复杂度应为nlogn,使用stable_sort(),时间复杂度为nlogn。sort()时间复杂度不总为nlogn。 #include #include #include #include using namespace std;
Downtown Disney District - 商业闹市
Downtown Disney District - 商业闹市 https://disneyland.disney.go.com/destinations/downtown-disney-district/ Visit a lively promenade featuring distinctive eateries, unique shops and exciting entertainmen...
股市快速下跌对楼市影响(转自易宪容的博客)
从1991年房地产企业万科在A股上市以来,目前国内有房地产公司在股市上市达到120多家。特别是随着2006年以来国内股市的繁荣,国内房地产企业更是借助上市、股市增发、发债、并购等方式从股市融资到1200多亿元。这是历年以来房地产企业在股市融资最大突破。不过,尽管是如此,房地产企业在股市所融集的资金占2007年房地产开发投资总额37256亿元的比重仍然只有3.2%。但是,我们也应该看到,房地产上
BRDF Explorer
记下一下: 学习PBR的好资源: BRDF Explorer 官网:https://www.disneyanimation.com/technology/brdf.html https://github.com/wdas/brdf/downloads https://github.com/wdas/brdf
Unity3D Shader编程】之十一 深入理解Unity5中的Standard Shader(三)&屏幕像素化特效的实现
本系列文章由@浅墨_毛星云 出品,转载请注明出处。   文章链接: http://blog.csdn.net/poem_qianmo/article/details/50095705 作者:毛星云(浅墨)    微博:http://weibo.com/u/1723155442 本文工程使用的Unity3D版本: 5.2.1 
java_disney
运用Java做的一个简单的Disney售票系统,
Disney Digest- Road to the Oscars Starts with Animation
Disney Digest- Road to the Oscars Starts with Animation
HDU 4114 Disney&#39;s FastPass Time
Disney's FastPass Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2403    Accepted Submission(s): 658 Problem DescriptionDisney's FastPass is
HDU4114 Disney's FastPass(floyd+状态压缩DP)旅游问题升级(难)
Disney's FastPass Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2117    Accepted Submission(s): 564 Problem Description Disney's
导出javadoc
so disney! 教你如何通过java 导出jni
Regarding Disney
Disney Princess     http://princess.disney.com/     1. MERIDA     2. Rapunzel     3. Ariel     4. Cinderella     5. Tiana     6. Belle     7. Pocahontas     8. Mulan     9. Snow White     1
基于物理着色:BRDF
知乎上难得的好文章,来自大牛,循序渐进,而且全,收藏! 作者:Maple 链接:https://zhuanlan.zhihu.com/p/21376124 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 在计算机图形学领域,着色(Shading)是指根据表面或者多边形相对光源和相机的角度和距离来计算它的颜色的过程。不同的用途可以使用不同的着色
东京迪斯尼海洋 Tokyo Disneysea 攻略
<br /><br />游乐项目<br />地中海港湾<br /> 位于乐园进门处,地中海港湾的游玩项目并不多,晚上八点的烟火晚会是在这里的湖面上进行。 <br />迪斯尼海洋渡轮航线  (7分钟 49人)<br /> 可以搭乘渡轮去失落河三角洲逛一圈,如果玩的累了就可以来这里休息休息,顺便拍拍河边的风景。 <br />威尼斯贡多拉游船  (11分钟 16人)<br /> 模仿威尼斯的贡多拉游船,有船夫撑篙划船,适合讲究情调的浪漫情侣。 <br />要塞探险<br /> 仿真的西班牙大帆船,船做
disney手繪教程
disney手繪教程,各種卡通畫法,頭部結構,骨架,動態和靜態...
Just Another Disney Problem
题目描述:J. Just Another Disney ProblemTime Limit: 1000msMemory Limit: 262144KB 64-bit integer IO format: %I64d Java class name: (Any) Submit Status PID: 49360 Input/Output: standard input/outputEvi
相关热词 c# mysql插入 c# sha256 加密 c#窗体上的叉添加事件 c#打印图片文件 c#後台調前台js c#控制台美化 c# 标记 浮点型 c#获取当前的农历日期 c# 构造函数重载 c# 页面功能注释