Pony.ai 有N个office分布在不同地方(编号从0开始），某些office之间有部署专线，office之间可以通过专线间接连接（专线是双向的），例如guagnzhou和beijing之间有专线，guagnzhou和shenzhen之间有专线，那么beijing可以通过guangzhou与shenzhen间接地通讯，这条信路的总延时是两条专线的延时之和。两个office之间的通讯延时是他们之间延时最短的信路的延时。
Infra团队知道当前任意两个office之间的通讯延时。最近Infra团队希望在office a与 office b之间部署一条新的专线，希望这条专线的延时 t 尽可能大（出于成本考虑）同时延时最大的两个office之间的通讯延时与 t 之和小于k，你能帮忙求出这个 t 吗？
[编程题]新增的专线
- 热度指数：655 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行一个正整数 N <= 1000，表示office的数目
接下来N行，每行N个非负整数，用空格分开。第i行第j个数表示当前office i和office j之间的通讯延时，保证小于1e9。
接下来一行3个整数，依次表示a，b，k。其中。
输出描述:
输出一行一个整数，满足条件的t，注意t不能是负数。如果不存在满足条件的t，输出 -1。
示例1
输入
3 0 2 3 2 0 5 3 5 0 1 2 3
输出
0
说明
增加从office 1 到 office 2 之间延时 t = 0 的专线后，延时最大的两个office之间的延时为2。 而 t + 2 < 3 满足题意
暂无题解
问题信息
通过挑战的用户
-
2022-10-22 11:18:54 -
2022-10-05 12:24:54
-
2022-10-05 11:36:27
-
2022-09-20 04:05:23
-
2022-09-16 18:56:06
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
