首页 > 试题广场 >

修复公路

[编程题]修复公路
  • 热度指数：104 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}某国在一场规模空前的大灾害过后，连接所有城市的公路都遭到了损坏而无法通车。政府派人修复这些公路。

\hspace{15pt}给出该国的城市数 N 和公路数 M，公路是双向的。并告诉你每条公路的连着哪两个城市以及什么时候能修完这条公路。询问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入描述:
\hspace{15pt}输入的第一行包含两个正整数 N\left(1 \leqq N \leqq 10^3\right),M\left(1 \leqq M \leqq 10^5\right)，分别表示某国的城市数和公路数。
 
\hspace{15pt}接下来 M 行，每行三个正整数 x,y\left( 1 \leqq x,y \leqq N\right),t \left( 1 \leqq t \leqq 10^5 \right)，表示存在一条连着 x,y 两个城市的，需要花费时间 t 来完成修复的公路。


输出描述:
\hspace{15pt}如果全部公路修复完毕仍然存在两个城市无法通车，则输出 -1，否则输出最早什么时候可以使得任意两个城市都能够通车。
示例1

输入

4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出

5
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-02 14:17:37
题目链接 修复公路 题目描述 在一个国家中，有 个城市和 条双向公路。一场灾害后，所有公路都被损坏。 对于每条公路，我们知道它连接的两个城市以及修复它所需的时间。 你需要找出最早的时刻，使得任意两个城市之间都能够互相到达（直接或间接通过已修复的公路）。如果即使所有公路都修复完毕，图仍不连通，则输 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 西行寺幽幽子
发表于 2025-08-08 21:39:57
题解：BISHI104 修复公路 题目链接 修复公路 题目描述 给定 个城市与 条双向公路，每条公路连接 并在时间 修复完成。求最早的时间使得任意两城市之间连通；若所有公路修复后仍不连通，输出 。 解题思路 按修复时间从小到大将公路排序，用并查集逐条合并。首次使所有城市处于同一连通块的时间即 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
1条回答 29浏览

热门推荐

相关试题

修复公路

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号