P1119 灾后重建

    • 2.2K通过
    • 6.8K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 图论 最短路 枚举,暴力 生成树 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    $B$ 地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的公路均无法通车。换句话说,只有连接着两个重建完成的村庄的公路才能通车,只能到达重建完成的村庄。

    题目描述

    给出 $B$ 地区的村庄数 $N$ ,村庄编号从 $0$ 到 $N-1$ ,和所有 $M$ 条公路的长度,公路是双向的。并给出第 $i$ 个村庄重建完成的时间 $t_i$ ,你可以认为是同时开始重建并在第 $t_i$ 天重建完成,并且在当天即可通车。若 $t_i$ 为 $0$ 则说明地震未对此地区造成损坏,一开始就可以通车。之后有 $Q$ 个询问 $(x, y, t)$ ,对于每个询问你要回答在第 $t$ 天,从村庄 $x$ 到村庄y的最短路径长度为多少。如果无法找到从 $x$ 村庄到 $y$ 村庄的路径,经过若干个已重建完成的村庄,或者村庄 $x$ 或村庄 $y$ 在第t天仍未重建完成 ,则需要返回 $-1$ 。

    输入输出格式

    输入格式:

    第一行包含两个正整数 $N,M$ ,表示了村庄的数目与公路的数量。

    第二行包含 $N$ 个非负整数 $t_0, t_1,…, t_{N-1}$ ,表示了每个村庄重建完成的时间,数据保证了 $t_0 ≤ t_1 ≤ … ≤ t_{N-1}$ 。

    接下来 $M$ 行,每行 $3$ 个非负整数 $i, j, w$ , $w$ 为不超过 $10000$ 的正整数,表示了有一条连接村庄 $i$ 与村庄 $j$ 的道路,长度为 $w$ ,保证 $i≠j$ ,且对于任意一对村庄只会存在一条道路。

    接下来一行也就是 $M+3$ 行包含一个正整数 $Q$ ,表示 $Q$ 个询问。

    接下来 $Q$ 行,每行 $3$ 个非负整数 $x, y, t$ ,询问在第 $t$ 天,从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少,数据保证了 $t$ 是不下降的。

    输出格式:

    共 $Q$ 行,对每一个询问 $(x, y, t)$ 输出对应的答案,即在第 $t$ 天,从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果在第t天无法找到从 $x$ 村庄到 $y$ 村庄的路径,经过若干个已重建完成的村庄,或者村庄x或村庄 $y$ 在第 $t$ 天仍未修复完成,则输出 $-1$ 。

    输入输出样例

    输入样例#1: 复制
    4 5
    1 2 3 4
    0 2 1
    2 3 1
    3 1 2
    2 1 4
    0 3 5
    4
    2 0 2
    0 1 2
    0 1 3
    0 1 4
    输出样例#1: 复制
    -1
    -1
    5
    4

    说明

    对于 $30\%$ 的数据,有 $N≤50$ ;

    对于 $30\%$ 的数据,有 $t_i= 0$ ,其中有 $20\%$ 的数据有 $t_i = 0$ 且 $N>50$ ;

    对于 $50\%$ 的数据,有 $Q≤100$ ;

    对于 $100\%$ 的数据,有 $N≤200$ , $M≤N \times (N-1)/2$ , $Q≤50000$ ,所有输入数据涉及整数均不超过 $100000$ 。

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