{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"Once upon a time, there was a traveler. \n\u003cbr\u003e\n\u003cbr\u003eHe plans to travel using stagecoaches (horse wagons). His starting point and destination are fixed, but he cannot determine his route. Your job in this problem is to write a program which determines the route for him. \n\u003cbr\u003e\n\u003cbr\u003e他计划乘公共马车旅行。他的出发点和目的地都定了,但他却无法确定路线。在这个问题中,你的工作是编写一个程序,为他确定路线。\u003cbr\u003e\n\u003cbr\u003eThere are several cities in the country, and a road network connecting them. If there is a road between two cities, one can travel by a stagecoach from one of them to the other. A coach ticket is needed for a coach ride. The number of horses is specified in each of the tickets. Of course, with more horses, the coach runs faster. \n\u003cbr\u003e\n\u003cbr\u003e这个国家有好几个城市,有一个连接它们的公路网。如果两个城市之间有一条公路,人们可以乘坐公共马车从其中一个城市到另一个城市。坐长途行程需要一张普通票。每张票中都指定了马的数量。当然,马越多,马车跑得越快。\n\u003cbr\u003e\n\u003cbr\u003eAt the starting point, the traveler has a number of coach tickets. By considering these tickets and the information on the road network, you should find the best possible route that takes him to the destination in the shortest time. The usage of coach tickets should be taken into account. \n\u003cbr\u003e\n\u003cbr\u003e在起点,旅行者有一些长途行程的票。通过考虑这些票和道路网络上的信息,你应该找到在最短时间内把他带到目的地的最好的可能路线。应该考虑到长途马车票的使用。\n\u003cbr\u003e\n\u003cbr\u003eThe following conditions are assumed. \n\u003cbr\u003e\u003cul\u003e\u003cli\u003eA coach ride takes the traveler from one city to another directly connected by a road. In other words, on each arrival to a city, he must change the coach. 长途汽车把旅行者从一个城市带到另一个由公路直接连接的城市。换句话说,每次到达一个城市,他都必须换乘长途马车。\n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eOnly one ticket can be used for a coach ride between two cities directly connected by a road. 在由公路直接连接的两个城市之间乘坐长途马车只能使用一张车票。\n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eEach ticket can be used only once. 每张票只能使用一次。\n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eThe time needed for a coach ride is the distance between two cities divided by the number of horses. 乘长途马车所需要的时间是两个城市之间的距离除以马匹的数量。\n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eThe time needed for the coach change should be ignored.更换长途所需的时间可以忽略。 \u003c/li\u003e\u003c/ul\u003e\n\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input consists of multiple datasets, each in the following format. The last dataset is followed by a line containing five zeros (separated by a space). \n\u003cbr\u003e\n\u003cbr\u003en m p a b\n\u003cbr\u003et1 t2 ... tn\n\u003cbr\u003ex1 y1 z1\n\u003cbr\u003ex2 y2 z2\n\u003cbr\u003e...\n\u003cbr\u003exp yp zp\n\u003cbr\u003e\n\u003cbr\u003eEvery input item in a dataset is a non-negative integer. If a line contains two or more input items, they are separated by a space. \n\u003cbr\u003e\n\u003cbr\u003e数据集中的每个输入项都是非负整数。如果一行包含两个或多个输入项,则它们用一个空格隔开。\u003cbr\u003e\n\u003cbr\u003en is the number of coach tickets. You can assume that the number of tickets is between 1 and 8. m is the number of cities in the network. You can assume that the number of cities is between 2 and 30. p is the number of roads between cities, which may be zero. \n\u003cbr\u003e\n\u003cbr\u003en是长途车票的票数。你可以假设票的数量在1到8之间。m是网络中城市的数量。你可以假设城市的数量在2到30之间。P是城市之间的道路数量,可以为0。\u003cbr\u003e\n\u003cbr\u003ea is the city index of the starting city. b is the city index of the destination city. a is not equal to b. You can assume that all city indices in a dataset (including the above two) are between 1 and m. \n\u003cbr\u003e\n\u003cbr\u003ea为起始城市的城市指数。B为目的城市的城市指数。a不等于b。你可以假设一个数据集(包括上面的两个)中所有的城市索引都在1到m之间。\u003cbr\u003e\n\n\u003cbr\u003eThe second line of a dataset gives the details of coach tickets. ti is the number of horses specified in the i-th coach ticket (1\u0026lt;\u003di\u0026lt;\u003dn). You can assume that the number of horses is between 1 and 10. \n\u003cbr\u003e\n\u003cbr\u003e数据集的第二行给出了长途车票的详细信息。Ti是第i张车票中指定的马数(1\u003c\u003di\u003c\u003dn)。你可以假设马的数量在1到10之间。\u003cbr\u003e\n\u003cbr\u003eThe following p lines give the details of roads between cities. The i-th road connects two cities with city indices xi and yi, and has a distance zi (1\u0026lt;\u003di\u0026lt;\u003dp). You can assume that the distance is between 1 and 100. \n\u003cbr\u003e\n\u003cbr\u003e下面的p行给出了城市之间道路的详细信息。第i条路连接两个城市,城市指数xi和yi,距离zi (1\u003c\u003di\u003c\u003dp)。你可以假设距离在1和100之间。\u003cbr\u003e\n\u003cbr\u003eNo two roads connect the same pair of cities. A road never connects a city with itself. Each road can be traveled in both directions. \n\u003cbr\u003e没有两条路连接同一对城市。道路永远不会把一个城市和它自己连接起来。每条路都可以在两个方向上行走。\n\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces. \n\u003cbr\u003e\n对于输入中的每个数据集,应该输出一行,如下所示。输出行不应该包含额外的字符,比如空格。\n\n\u003cbr\u003eIf the traveler can reach the destination, the time needed for the best route (a route with the shortest time) should be printed. The answer should not have an error greater than 0.001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied. \n如果旅行者能够到达目的地,那么应该打印出最佳路线(时间最短的路线)所需的时间。答案的误差不应大于0.001。在满足上述精度条件的情况下,您可以输出小数点后的任意数位。\n\u003cbr\u003e\n\u003cbr\u003eIf the traveler cannot reach the destination, the string \"Impossible\" should be printed. One cannot reach the destination either when there are no routes leading to the destination, or when the number of tickets is not sufficient. Note that the first letter of \"Impossible\" is in uppercase, while the other letters are in lowercase. \n\u003cbr\u003e如果旅行者无法到达目的地,则应打印“Impossible”字符串。一个人不能到达目的地,要么是没有通往目的地的路线,要么是票的数量不够。请注意,“Impossible”的第一个字母是大写的,而其他字母是小写的。"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4 3 1 4\n3 1 2\n1 2 10\n2 3 30\n3 4 20\n2 4 4 2 1\n3 1\n2 3 3\n1 3 3\n4 1 2\n4 2 5\n2 4 3 4 1\n5 5\n1 2 10\n2 3 10\n3 4 10\n1 2 0 1 2\n1\n8 5 10 1 5\n2 7 1 8 4 5 6 3\n1 2 5\n2 3 4\n3 4 7\n4 5 3\n1 3 25\n2 4 23\n3 5 22\n1 4 45\n2 5 51\n1 5 99\n0 0 0 0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e30.000\n3.667\nImpossible\nImpossible\n2.856\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Since the number of digits after the decimal point is not specified, the above result is not the only solution. For example, the following result is also acceptable. \n\u003cbr\u003e\n由于小数点后的位数没有指定,所以上面的结果不是唯一的解。例如,下面的结果也是可以接受的。\n\n\u003cbr\u003e\u003cpre\u003e30.0\n\u003cbr\u003e3.66667\n\u003cbr\u003eImpossible\n\u003cbr\u003eImpossible\n\u003cbr\u003e2.85595\u003c/pre\u003e"}}]}