首页 > 试题广场 > 新增的专线
[编程题]新增的专线
  • 热度指数:513 时间限制: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 满足题意
首先,假如一开始给的距离表确实已经是每两点的最短距离了。如果我们改变给定的a和b之间的距离(假设改到d),那么对于每对点i和点j,它们这时候的实际最短距离为min(table[i][j], table[i][a] + d + table[b][j], table[i][b] + d + table[a][j])。
于是可以用binary search来假设a和b的距离,按上述方法代入每对点i和点j,来看是否能符合要求。Time complexity: O(N^2 log k), Space complexity: O(N^2).
这方法试了结果通过。

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;cin>>n;
    vector<vector<int> > edges;
    for(int i=0;i<n;i++){
        vector<int> row;
        for(int j=0;j<n;j++){
            int cur;cin>>cur;row.push_back(cur);
        }
        edges.push_back(row);
    }
    int a,b,k;cin>>a>>b>>k;
    int lower = -1,upper = k;
    while(upper-lower>1){
        int mid = (upper+lower)/2,ok=1;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int d = edges[i][j];
                d = min(d,edges[i][a] + edges[b][j] + mid);
                d = min(d,edges[i][b] + edges[a][j] + mid);
                if(d+mid>=k){
                    ok=0;
                    break;
                }
            }
            if(!ok)break;
        }
        if(!ok)upper = mid;
        else lower = mid;
    }
    cout<<lower<<endl;
    return 0;
}


编辑于 2020-07-14 03:56:26 回复(23)
N = int(input())
o = [[int(i) for i in input().split(" ")] for _ in range(N)] # office
a, b, k = [int(i) for i in input().split(" ")]
left = -1
right = k
while right-left > 1:
    mid = (left + right) // 2
    maxDelay = 0
    for i in range(N):
        for j in range(i,N):
            if i == a and j == b:
                maxDelay = max(maxDelay, mid)
            else:
                maxDelay = max(maxDelay, min(o[i][j],o[i][a]+mid+o[b][j],o[i][b]+mid+o[a][j]))
            if maxDelay + mid >= k: break
        if maxDelay + mid >= k: break
    if maxDelay + mid < k:
        left = mid
    else:
        right = mid
print(left)
20% case 超时
发表于 2020-12-09 20:05:14 回复(0)

热门推荐

通过挑战的用户