{"trustable":false,"sections":[{"title":"题面","value":{"format":"MD","content":"从前,有一个旅行者。\n他计划乘坐驿车(马车)旅行。他的起点和终点都是固定的,但是他无法确定路线。在这个问题中,你的任务是为他编写一个确定路线的程序。\n在这个国家中有几个城市,有一个公路网将它们连接起来。如果在两个城市之间有一条公路,人们可以乘坐驿马车从一个城市到另一个城市。乘坐马车需要购买车票。每张车票都规定了马匹的数量。当然,马匹越多,马车跑得越快。\n在起点,旅客有若干长途汽车票。通过考虑这些车票和路网信息,您应该找到最佳路线,在最短时间内到达目的地。应考虑长途汽车票的使用情况。"}},{"title":"条件","value":{"format":"MD","content":"假设条件如下\n乘坐长途汽车从一个城市到另一个有公路直接连接的城市。换句话说,每次到达一个城市,旅客必须换乘长途汽车。\n在有公路直接相连的两个城市之间乘坐长途汽车只能使用一张车票。\n每张车票只能使用一次。\n乘坐马车所需的时间是两个城市之间的距离除以马匹的数量。\n马车换乘所需的时间应忽略不计。"}},{"title":"输入","value":{"format":"MD","content":"\n\n输入由多个数据集组成,每个数据集的格式如下。最后一个数据集后有一行包含5个零(用空格隔开)。\nn m p a b\nt1 t2 ... tn\nx1 y1 z1\nx2 y2 z2\n...\nxp yp zp\n数据集中的每个输入项都是一个非负整数。如果一行包含两个或多个输入项,则用空格隔开。\nn 是长途汽车票的数量。m是网络中的城市数量。p是城市间的道路数量,可能为零。\na是起始城市的城市指数。b是目的地城市的城市指数。a不等于b。您可以假设数据集中的所有城市指数(包括上述两个)都在1和m之间。\nti是第i张长途汽车票中指定的马匹数量(1\u003c\u003di\u003c\u003dn)。可以假设马匹数量在1到10之间。\n下面p行给出了城市间道路的详细信息。第i条道路连接城市指数为xi和yi的两个城市,距离为zi(1\u003c\u003di\u003c\u003dp)。可以假设距离在1到100之间。\n没有两条道路连接同一对城市。一条道路永远不会连接一个城市和它自己。每条道路都可以双向通行。\n\n"}},{"title":"输出","value":{"format":"MD","content":"\n对于输入中的每个数据集,应按以下规定输出一行。输出行不应包含空格等额外字符。\n如果旅行者可以到达目的地,应打印最佳路线(时间最短的路线)所需的时间。答案的误差不应大于0.001。在满足上述精度条件的前提下,小数点后的数字可以任意输出。\n如果旅行者无法到达目的地,则应打印字符串 \"Impossible\"(不可能)。如果没有通往目的地的路线或车票数量不足,则无法到达目的地。注意 \"Impossible \"的第一个字母为大写,其他字母为小写。"}},{"title":"Sample","value":{"format":"MD","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":"提示","value":{"format":"MD","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"}}]}