给你一个无向图, 个顶点, 条边,每条边有一个权值 。给你两个顶点 和 ,求一条路径,使得路径上最大边和最小边的比值最小。如果 和 之间没有路径,输出 IMPOSSIBLE,否则输出这个比值,如果需要,表示成一个既约分数。 备注:两个顶点之间可能有多条路径。
IMPOSSIBLE
第一行包含两个正整数, 和 。 接下来的 行每行包含三个正整数:, 和 ,表示景点 到景点 之间有一条双向公路,车辆必须以速度 在该公路上行驶。最后一行包含两个正整数 ,,表示想知道从景点 到景点 最大最小速度比最小的路径。 和 不可能相同。
如果景点 到景点 没有路径,输出 IMPOSSIBLE。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。
4 2 1 2 1 3 4 2 1 4
3 3 1 2 10 1 2 5 2 3 8 1 3
5/4
3 2 1 2 2 2 3 4 1 3
2
对于 的数据,,,。