首页 / 题库

P15168 - 旅行

数据结构入门
通过次数0 提交次数0 内存限制 128MB 时间限制1秒

描述

Z 小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 $n$ 个景点(编号为 $1,2,3,\ldots,n$),这些景点被 $m$ 条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。

也许是为了保护该地的旅游资源,Z 小镇有个奇怪的规定,就是对于一条给定的公路 $r_i$,任何在该公路上行驶的车辆速度必须为 $v_i$。

速度变化太快使得游客们很不舒服,因此从一个景点前往另一个景点的时候,大家都希望选择行驶过程中最大速度和最小速度的比尽可能小的路线,也就是所谓最舒适的路线。

输入

第一行包含两个正整数 $n,m$。

接下来的 $m$ 行每行包含三个正整数 $x,y,v$。表示景点 $x$ 到景点 $y$ 之间有一条双向公路,车辆必须以速度 $v$ 在该公路上行驶。

最后一行包含两个正整数 $s,t$,表示想知道从景点 $s$ 到景点 $t$ 最大最小速度比最小的路径。$s$ 和 $t$ 不可能相同。

输出

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

样例

  • 复制
  • 复制

提示

对于 $100\%$ 的数据,$1 \le x,y \le n \le 500$,$1 \le v < 3 \times 10^4$,$1 \le m \le 5 \times 10^3$,$x \ne y$。

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36