编程介的小学生 2019-08-31 22:42 采纳率: 20.5%
浏览 103

Playground Hideout 用C语言

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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 怎么在stm32门禁成品上增加记录功能
    • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
    • ¥50 NT4.0系统 STOP:0X0000007B
    • ¥15 想问一下stata17中这段代码哪里有问题呀
    • ¥15 flink cdc无法实时同步mysql数据
    • ¥100 有人会搭建GPT-J-6B框架吗?有偿
    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号