{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003e他计划乘公共马车旅行。他的出发点和目的地都定了,但他却无法确定路线。在这个问题中,你的工作是编写一个程序,为他确定路线。\u003cbr\u003e\n\u003cbr\u003e这个国家有好几个城市,有一个连接它们的公路网。如果两个城市之间有一条公路,人们可以乘坐公共马车从其中一个城市到另一个城市。坐长途行程需要一张普通票。每张票中都指定了马的数量。当然,马越多,马车跑得越快。\n\u003cbr\u003e\n\u003cbr\u003e在起点,旅行者有一些长途行程的票。通过考虑这些票和道路网络上的信息,你应该找到在最短时间内把他带到目的地的最好的可能路线。应该考虑到长途马车票的使用。\n\u003cbr\u003e长途汽车把旅行者从一个城市带到另一个由公路直接连接的城市。换句话说,每次到达一个城市,他都必须换乘长途马车。\n\u003cbr\u003e在由公路直接连接的两个城市之间乘坐长途马车只能使用一张车票。\n\u003cbr\u003e 每张票只能使用一次。\n\u003cbr\u003e乘长途马车所需要的时间是两个城市之间的距离除以马匹的数量。\n\u003cbr\u003e更换长途所需的时间可以忽略.\n\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\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\u003e数据集中的每个输入项都是非负整数。如果一行包含两个或多个输入项,则它们用一个空格隔开。\u003cbr\u003e\n\u003cbr\u003en是长途车票的票数。你可以假设票的数量在1到8之间。m是网络中城市的数量。你可以假设城市的数量在2到30之间。P是城市之间的道路数量,可以为0。\u003cbr\u003e\n\u003cbr\u003ea为起始城市的城市指数。B为目的城市的城市指数。a不等于b。你可以假设一个数据集(包括上面的两个)中所有的城市索引都在1到m之间。\u003cbr\u003e\n\u003cbr\u003e数据集的第二行给出了长途车票的详细信息。Ti是第i张车票中指定的马数(1\u003c\u003di\u003c\u003dn)。你可以假设马的数量在1到10之间。\u003cbr\u003e\n\u003cbr\u003e下面的p行给出了城市之间道路的详细信息。第i条路连接两个城市,城市指数xi和yi,距离zi (1\u003c\u003di\u003c\u003dp)。你可以假设距离在1和100之间。\u003cbr\u003e\n\u003cbr\u003e没有两条路连接同一对城市。道路永远不会把一个城市和它自己连接起来。每条路都可以在两个方向上行走。\n\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于输入中的每个数据集,应该输出一行,如下所示。输出行不应该包含额外的字符,比如空格。\n如果旅行者能够到达目的地,那么应该打印出最佳路线(时间最短的路线)所需的时间。答案的误差不应大于0.001。在满足上述精度条件的情况下,您可以输出小数点后的任意数位。\n\u003cbr\u003e\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":"由于小数点后的位数没有指定,所以上面的结果不是唯一的解。例如,下面的结果也是可以接受的。\n\n\u003cbr\u003e\u003cpre\u003e30.0\n\u003cbr\u003e3.66667\n\u003cbr\u003eImpossible\n\u003cbr\u003eImpossible\n\u003cbr\u003e2.85595\u003c/pre\u003e"}}]}