Playground Hideout

Problem Description
Little Timmy likes playgrounds, especially those with complicated constructions of wooden towers interconnected with plank bridges or ropes, with slides and rope-ladders. He could play on his favourite playground for days, if only his parents let him. Sooner or later they decide that it is time to go home. For their next trip to a playground Timmy has a plan: he will not simply let his father grab him, but climb to the highest platform of the most complex structure and hide there. His father will never be able to reach him there or at least it will give Timmy some extra time.
An adventure playground consists of several platforms. The difficulty of reaching a platform directly from ground level varies. In addition the different platforms are interconnected by “bridges” of different difficulty. There are connections that can be used a lot more easily in one direction than in the other, e.g. slides. Given a plan of an adventure playground you need to help Timmy find the platform that is most difficult to reach from ground level. The difficulty for a path in the adventure playground can be estimated as a sum of the difficulties of the connections used. The difficulty of reaching a platform is the difficulty of the least difficult path from ground level to the platform.

Input
The input starts with a line containing a single integer n, the number of test cases. Each test case starts with a line containing two integers 1 <= p, c <= 10000, the number of platforms and connections respectively (we allow for large playgrounds). A line with p integers pi ∈ [0, 1000] follows, where pi is the difficulty of reaching platform i directly from ground-level. The next c lines each describe a connection between two platforms. They consist of four integers i, j, a, b; i < j, the zero-based index of the two connected
platforms and the difficulties a ∈[0, 1000] and b ∈ [0, 1000] of using the connection to get from pi to pj and from pj to pi respectively. There can be multiple connections between any two platforms.

Output
The output for every test case begins with a line containing “Scenario #i:”, where i is the number of the test case counting from 1. Then, output a single line containing the zero-based index of the platform that is most difficult to reach from ground level. If two or more platforms are equally difficult to reach, output the smallest index of among those platforms. Terminate each test case with an empty line.

Sample Input
2
4 3
1 10 10 40
0 3 3 2
1 3 4 3
2 3 5 4
2 2
11 10
0 1 2 2
0 1 1 0

Sample Output
Scenario #1:
2

Scenario #2:
0

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
这是一段测试的问题,测试的问题
3
求解:用vue、weex做的项目,为什么在手机上用weex playground app预览出来的效果很糟糕。请看详细描述⬇。
2
ros的gazebo和rviz联合仿真,rviz添加控件之后,gazebo闪退
0
运用C语言,先按照第一个数字的大小进行比较,若第一个数字大小相同,则按照第二个比较,依次类推
0
碰撞的计算的算法的问题,怎么利用C语言的程序的设计的方式来实现的?
0
C语言按照第一个数字的大小进行比较,若第一个相同,则按照第二个数字大小进行比较
0
计算游乐场的圆环的半径的应用问题,怎么使用C语言的程序的代码的编写的过程去实现呢?
0
给定字段的配置然后计算环的半径,怎么用C语言的程序的编写的过程的实现的方式是什么
0
BabylonJs加载stl文件,报错Uncaught RangeError: Invalid typed array length: 9065025882
0
选择难度最小的路径的计算,怎么使用C语言的程序的设计的代码的编写去解决这个问题
0
如何才能选择最小难度的路径的计算,具体如何使用C语言的程序的设计的代码的编写去解决这个问题
0
Playground程序是如何设计的呢
0
D Tree 程序的设计
0
Quoit Design的程序 的设计
0
用C语言来制作一个D Tree
0
Playground Hideout 用C语言
0
Playground Hideout 怎么实现
0
Playground 具体到程序的写法
0
Playground Hideout 解答
0
Playground 怎么去实现的