首页 > 试题广场 >

新增的专线

[编程题]新增的专线
  • 热度指数：655 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
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 吗？

输入描述:
第一行一个正整数 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 满足题意
算法知识视频讲解
添加回答
Python
李peak头像 李peak 
import sys
n=map(int, sys.stdin.readline().split())[0]
matrix=[]
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().split())))
offa, offb, k=map(int, sys.stdin.readline().split())

left=-1
right=k
while right-left>1:
    mid=(right+left)//2
    flag=True
    for i in range(n):
        for j in range(n):
            d=min([matrix[i][j], 
                   matrix[i][offa]+mid+matrix[offb][j],
                   matrix[i][offb]+mid+matrix[offa][j]])
            if d+mid>=k:
                flag=False
                break
        if not flag:
            break
    if flag:
        left=mid
    else:
        right=mid
print(left)
还是超时。

二分查找，对于每个元素更新其最短路径值，然后判断该值是否已经不满足条件了，可以剪枝。
发表于 2021-04-04 20:57:10 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 测试开发工程师 2019 大数据开发工程师 小马智行 数据分析师 Java工程师
上传者：小小
难度：
1条回答 5201浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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