P2245 星际导航

    • 328通过
    • 1.1K提交
  • 题目提供者 mhlwsk
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    $\text{sideman}$ 做好了回到 $\text{Gliese}$ 星球的硬件准备,但是 $\text{sideman}$ 的导航系统还没有完全设计好。为了方便起见,我们可以认为宇宙是一张有 $N$ 个顶点和 $M$ 条边的带权无向图,顶点表示各个星系,两个星系之间有边就表示两个星系之间可以直航,而边权则是航行的危险程度。

    $\text{sideman}$ 现在想把危险程度降到最小,具体地来说,就是对于若干个询问 $(A, B)$,$\text{sideman}$ 想知道从顶点 $A$ 航行到顶点 $B$ 所经过的最危险的边的危险程度值最小可能是多少。作为 $\text{sideman}$ 的同学,你们要帮助 $\text{sideman}$ 返回家园,兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

    输入输出格式

    输入格式:

    第一行包含两个正整数 $N$ 和 $M$,表示点数和边数。

    之后 $M$ 行,每行三个整数 $A$,$B$ 和 $L$,表示顶点 $A$ 和 $B$ 之间有一条边长为 $L$ 的边。顶点从 $1$ 开始标号。

    下面一行包含一个正整数 $Q$,表示询问的数目。

    之后 $Q$ 行,每行两个整数 $A$ 和 $B$,表示询问 $A$ 和 $B$ 之间最危险的边危险程度的可能最小值。

    输出格式:

    对于每个询问, 在单独的一行内输出结果。如果两个顶点之间不可达, 输出 $\text{impossible}$。

    输入输出样例

    输入样例#1: 复制
    4 5
    1 2 5
    1 3 2
    2 3 11
    2 4 6
    3 4 4
    3
    2 3
    1 4
    1 2
    
    输出样例#1: 复制
    5
    4
    5
    

    说明

    对于 $40\%$ 的数据,满足 $N \leq 1000, M \leq 3000, Q \leq 1000$。

    对于 $80\%$ 的数据,满足 $N \leq 10000, M \leq 10^5, Q \leq 1000$。

    对于 $100\%$ 的数据,满足 $N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9$。数据不保证没有重边和自环。

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