{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"从前,有一个旅行者。\r\u003cbr\u003e\r\u003cbr\u003e他计划乘坐马车(马车)旅行。他的出发点和目的地是固定的,但他无法确定自己的路线。在这个问题中,你的任务是编写一个程序,确定他的路线。\r\u003cbr\u003e\r\u003cbr\u003e这个国家有几个城市,它们之间有一条连接它们的道路网络。如果两个城市之间有一条道路,那么一个人可以乘坐马车从其中一个城市到另一个城市。乘坐马车需要一张车票。每张车票上都注明了马匹的数量。当然,马匹越多,马车就跑得越快。\r\u003cbr\u003e\r\u003cbr\u003e在出发点,旅行者有一些马车票。通过考虑这些车票和道路网络上的信息,你应该找到一个最佳路线,以最短的时间将他带到目的地。应考虑车票的使用情况。\r\u003cbr\u003e\r\u003cbr\u003e假设以下条件。\r\u003cbr\u003e\u003cul\u003e\u003cli\u003e一次马车乘坐将旅行者从一个城市直接连接到另一个城市。换句话说,每到达一个城市,他必须换乘马车。\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e在两个直接连接的城市之间的马车乘坐只能使用一张车票。\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e每张车票只能使用一次。\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e马车乘坐所需的时间是两个城市之间的距离除以马匹的数量。\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e应忽略换乘马车所需的时间。\u003c/li\u003e\u003c/ul\u003e\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入由多个数据集组成,每个数据集的格式如下。最后一个数据集后面跟着一行包含五个零(用空格分隔)的行。\r\u003cbr\u003e\r\u003cbr\u003en m p a b\r\u003cbr\u003et1 t2 ... tn\r\u003cbr\u003ex1 y1 z1\r\u003cbr\u003ex2 y2 z2\r\u003cbr\u003e...\r\u003cbr\u003exp yp zp\r\u003cbr\u003e\r\u003cbr\u003e数据集中的每个输入项都是非负整数。如果一行包含两个或更多输入项,则它们之间用空格分隔。\r\u003cbr\u003e\r\u003cbr\u003en是马车票的数量。可以假定车票数量在1到8之间。m是网络中的城市数量。可以假定城市数量在2到30之间。p是城市之间的道路数量,可能为零。\r\u003cbr\u003e\r\u003cbr\u003ea是出发城市的城市索引。b是目的地城市的城市索引。a不等于b。可以假定数据集中所有城市索引(包括上述两个)在1到m之间。\r\u003cbr\u003e\r\u003cbr\u003e数据集的第二行给出了马车票的详细信息。ti是第i张车票上指定的马匹数量(1≤i≤n)。可以假定马匹数量在1到10之间。\r\u003cbr\u003e\r\u003cbr\u003e接下来的p行给出了城市之间道路的详细信息。第i条道路连接两个城市,城市索引为xi和yi,并且距离为zi(1≤i≤p)。可以假定距离在1到100之间。\r\u003cbr\u003e\r\u003cbr\u003e没有两条道路连接相同的一对城市。一条道路永远不会连接一个城市与自身。每条道路可以双向行驶。"}},{"title":"输出","value":{"format":"HTML","content":"对于输入中的每个数据集,应输出一行,如下所示。输出行不应包含额外的字符,如空格。\r\u003cbr\u003e\r\u003cbr\u003e如果旅行者可以到达目的地,则应打印出最佳路线所需的时间(最短时间的路线)。答案不应有大于0.001的误差。可以输出小数点后的任意位数,只要满足上述精度条件。\r\u003cbr\u003e\r\u003cbr\u003e如果旅行者无法到达目的地,则应打印字符串“Impossible”。当没有通往目的地的路线时,或者车票数量不足时,都无法到达目的地。请注意,“Impossible”的第一个字母大写,其他字母小写。\r\u003cbr\u003e"}},{"title":"样例","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\r\n3 1 2\r\n1 2 10\r\n2 3 30\r\n3 4 20\r\n2 4 4 2 1\r\n3 1\r\n2 3 3\r\n1 3 3\r\n4 1 2\r\n4 2 5\r\n2 4 3 4 1\r\n5 5\r\n1 2 10\r\n2 3 10\r\n3 4 10\r\n1 2 0 1 2\r\n1\r\n8 5 10 1 5\r\n2 7 1 8 4 5 6 3\r\n1 2 5\r\n2 3 4\r\n3 4 7\r\n4 5 3\r\n1 3 25\r\n2 4 23\r\n3 5 22\r\n1 4 45\r\n2 5 51\r\n1 5 99\r\n0 0 0 0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e30.000\r\n3.667\r\nImpossible\r\nImpossible\r\n2.856\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"由于未指定小数点后的位数,上述结果并非唯一解。例如,以下结果也是可以接受的。\r\u003cbr\u003e\r\u003cbr\u003e\u003cpre\u003e30.0\r\u003cbr\u003e3.66667\r\u003cbr\u003eImpossible\r\u003cbr\u003eImpossible\r\u003cbr\u003e2.85595\u003c/pre\u003e"}}]}