UC知道一道PASCAL题目
来源：百度知道 编辑：UC知道 时间：2024/05/28 09:53:00
有N个房间，你要从最左边走到最右边。有一些房间不可到达，走入每一个房间都有一定的代价。
每个房间都有一个特征值，如果这个特征值是-1则不能进入。
你可以从一个房间走到他左边或右边的房间里，这时，代价就是你走入房间的特征值。还可以用传送器。传送其数量有限，且只能从某个特定的房间传送到另一个房间。当时用传送器的时候，要花费x+teleportprice的代价。其中x表示你用过几次传送器。
现在要计算从左边到右边的最小花费。在满足花费最小的情况下，你还要计算最小的步数（传送一次也算一步）。房间从做到优，从0开始编号.
Input
第一行：3个整数，N房间数量，M传送器数量，teleportprice如题描述
第二行：N个整数，表示房间的特征值。
第三行到第（M+2）行：每行两个整数，a,b，表示传送器能从房间A传送到房间B。
Output
如果可以到右边，输出两行，第一行为最小花费，第二行为最小步数。否则输出-1。
Example Input
4 1 1000
0 -1 0 0
0 2
Example Output
1000
2
N<=50,M<=50,0<=teleportprice<=1000,-1<=特征值<=1000
每个房间都有一个特征值，如果这个特征值是-1则不能进入。
你可以从一个房间走到他左边或右边的房间里，这时，代价就是你走入房间的特征值。还可以用传送器。传送其数量有限，且只能从某个特定的房间传送到另一个房间。当时用传送器的时候，要花费x+teleportprice的代价。其中x表示你用过几次传送器。
现在要计算从左边到右边的最小花费。在满足花费最小的情况下，你还要计算最小的步数（传送一次也算一步）。房间从做到优，从0开始编号.
Input
第一行：3个整数，N房间数量，M传送器数量，teleportprice如题描述
第二行：N个整数，表示房间的特征值。
第三行到第（M+2）行：每行两个整数，a,b，表示传送器能从房间A传送到房间B。
Output
如果可以到右边，输出两行，第一行为最小花费，第二行为最小步数。否则输出-1。
Example Input
4 1 1000
0 -1 0 0
0 2
Example Output
1000
2
N<=50,M<=50,0<=teleportprice<=1000,-1<=特征值<=1000
首先无视传送器,求出从从任意一个房间走到另一个房间的最小花费以及步数
然后在此基础上求出使用一次传送器、2次、三次...的任意两个房间之间的花费以及步数
直到继续使用传送器不能带来任何好处为止
显然最多使用n次传感器，所以时间效率还行