消防车调度某城市消防部门与交通部门合作维护反映当前城市街道状况的地图。在规定的某天里，一些街道将由于修复或施工而被关闭。消防队员需要能够选择从消防站到火警地点的不经过被关闭街道的路线。城市被划分成为不重叠的消防区，每区设有一个消防站。当火警发生时，一个中央调度站向火警地点所在的消防站发出警报并向其提供一个从该消防站到火警地点的路线。1 输入城市的每个消防区有一个独立的地图。每张地图的街区用小于21的正整数标识。消防站总是在街区#1。输入文件包括一些测试项，代表在不同街区发生的不同的火警。测试项的第一行均表示离火警最近街区的编号。接下来若干行由用空格隔开的表示开放的街道所邻接的街区的正整数对组成。（例如，如果数对 4 7 是文件中的一行，那么街区4 和7 之间的街道是开放的。在街区4 和7 之间的路段上没有其他街区。）每个测试项的最后一行由一个0数。2 输出 对于每个测试项，你的输出必须用数字来标识测试项（case #1, case #2，等等）。输出必须将每条路线列在不同的行上，街区按路线顺序依次写出。输出必须给出从消防站到火警地点的所有路线的总数。其中只包括那些不经过重复街区的路线（由于显而易见的理由，消防部门不希望他们的车子兜圈子）。不同测试项的输出必须出现在不同的行上。旅行预算一个旅行代理商经常被要求去估计开车从一个城市旅行至另一城市的最小费用。他有一个在通常路线上的大多数加油站的列表。列表包括了所有加油站的位置及当前每升汽油的价格。为了简化估计费用的过程，代理商使用了以下的简化汽车驾驶员行为的规则：（1）除非汽车无法用油箱里的汽油达到下一个加油站（如果有的话）或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。 （2）在每一个加油站停下的加油驾驶员总是将油箱加满。（3）在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上去花去2.00元。（4）在驶向加油站或目的地时，驾驶员不需要超过必需量的汽油。不需要“安全余量”。（5）驾驶员开始旅程时油箱总是满的。（6）在每个加油站付款时四舍五入到分（1元等于100分）（7）你必须写一个程序以估计驾驶员在旅程上至少要为汽油和食品付多少钱。1、输入程序的输入将由若干个对应不同的旅程的数据项组成，每个数据项由若干信息行组成。开始的2行给出了出发地和目的地的信息，数据项的后继行代表了路线上的加油站，每个加油站用一行表示。下面是输入数据项的精确格式及其含义。第一行：一个实数——从出发地到目的地的距离（公里）第二行：三个实数及一个整数。（1）第一个实数是汽车油箱的最大的容量（升）（2）第二个实数是汽车每升汽油可以行驶的英里数；（3）第三个实数是汽车在出发地城市加满油箱的费用（单位：元）；（4）整数（小于51）是路线上加油站的数目。接下来的每一行：两个实数：（1）第一个实数是从出发地到加油站的距离（单位：公里）；（2）第二个实数是该加油站出售的汽油每升的价格（单位：元）。数据项中的所有数据都是正的。一条路线上的加油站根据其到出发地的距离递增排列。路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。每条路线上的加油站都被适当地安排以使得任何汽车都能够从出发地开到目的地。输入数据中若某行为一个负数则表示输入数据结束。2 输出对于输入中的每个数据项，你的程序必须打印数据项编号以及一个给出了精确到分的汽油和食品的最小总费用。总费用必须包括开始时在出发地加满油箱的费用。