P2502 [HAOI2006]旅行

    • 259通过
    • 638提交
  • 题目提供者 thomasfangyi
  • 评测方式 云端评测
  • 标签 并查集 排序 枚举,暴力 各省省选 2006 河南 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Z小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点(编号为1,2,3,…,N),这些景点被M条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。也许是为了保护该地的旅游资源,Z小镇有个奇怪的规定,就是对于一条给定的公路Ri,任何在该公路上行驶的车辆速度必须为Vi。速度变化太快使得游客们很不舒服,因此从一个景点前往另一个景点的时候,大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线,也就是所谓最舒适的路线。

    输入输出格式

    输入格式:

    第一行包含两个正整数,N和M。

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

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

    输出格式:

    如果景点s到景点t没有路径,输出“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

    说明

    【数据范围】

    1<N≤500

    1≤x,y≤N,0<v<30000,x≠y

    0<M≤5000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。