链路可靠性

链路可靠性

【华为校园招聘软件】2021-08-08

【编程题目 | 300分】 [ 2021 校园招聘 考试题 ]

编程题 第3/3题

3、链路可靠性

• 为了提高网络的可靠性，网络中经常建设一些低速链路，对工作路径实现保护，但这些低速链路需要设置一个合理的开销值，以免正常条件下流量走到低速链路上，影响体验。
• 现在你的工作是评估网络中路径的最大开销，以确定新增路径的开销设置，只有当新增路径的开销大于当前最长路径的开销才能保证正常情况下网络流量不会走到低速链路上。
• 网络中链路均为有向链路，且不存在环路。

输入描述：

• 链路集合，每条链路由源节点，目的节点和边的权重表示，链路存在方向。
• 链路条数<= 200;边的权重<= 200。

如：

[[1,2,5],[1,3,5],[4,2,10],[2,5,5],[3,4,10],[3,7,10],[4,7,5],[5,6,5],[6,7,5]]

输出描述：

• 最长路径的开销值

如：

40

示例 1

输入

[[1,2,5],[1,3,5],[4,2,10],[2,5,5],[3,4,10],[3,7,10],[4,7,5],[5,6,5],[6,7,5]]

输出

40

解释：

路径节点为 ：1->3->4->2->5->6->7

最大总消耗为 ：5 + 10 + 10 + 5 + 5 + 5 = 40

C++

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
constexpr int N = 205;
int graph[N][N];

剩余50%内容，订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接