P1119 灾后重建

    • 3.9K通过
    • 12.1K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 图论 最短路 枚举,暴力 生成树 高性能
  • 难度 提高+/省选-
  • 时空限制 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类违反进行处理。