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 吗?