logo AlgoBeat OnlineJudge
登录 注册

#101050. [BZOJ 1050] [HAOI2006]旅行comf

内存限制:162 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给你一个无向图, 个顶点, 条边,每条边有一个权值 。给你两个顶点 ,求一条路径,使得路径上最大边和最小边的比值最小。如果 之间没有路径,输出 IMPOSSIBLE,否则输出这个比值,如果需要,表示成一个既约分数。
备注:两个顶点之间可能有多条路径。

输入格式

第一行包含两个正整数,
接下来的 行每行包含三个正整数:,表示景点 到景点 之间有一条双向公路,车辆必须以速度 在该公路上行驶。最后一行包含两个正整数 ,表示想知道从景点 到景点 最大最小速度比最小的路径。 不可能相同。

输出格式

如果景点 到景点 没有路径,输出 IMPOSSIBLE。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。

样例

样例输入 #1

4 2
1 2 1
3 4 2
1 4

样例输出 #1

IMPOSSIBLE

样例输入 #2

3 3
1 2 10
1 2 5
2 3 8
1 3

样例输出 #2

5/4

样例输入 #3

3 2
1 2 2
2 3 4
1 3

样例输出 #3

2

数据范围与提示

对于 的数据,