#1050. [HAOI2006]旅行comf

[HAOI2006]旅行comf

题目描述

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

输入格式

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

输出格式

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

4 2
1 2 1
3 4 2
1 4
IMPOSSIBLE
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

数据规模与约定

对于 100%100\% 的数据,1<n500,1x,yn1<n\leq500,1\leq x,y\leq n0<v<3×1040<v<3\times 10^40<m5×1030<m\leq5\times 10^3