mtngt11中兴迪杰斯特拉2019.7z

本次比赛时间精力有限，采用的算法简单，成绩不是很理想。 先来简单分析一下题目，本次比赛在一张拓扑图中，需要满足带宽的限制，为每一个请求安排一条路径连接起点到终点，计算出该路径成本，寻找总成本最优的结果。 首先，刚开始被比赛方带偏了，比赛方给出的请求的参考路径其实没什么用，仅仅使用这些路径数据分配，测试用例的总成本较优解也就500多w。 要想有效的降低成本结果，需要摒弃输入中提供的路径，所有路径都由自己去分配。 首先我想到的可能是用迪杰斯特拉算法等，逐一的找寻最优路径，再交换顺序重新分配。 又或者是每次随机的选择路径，分配完成后，再随机的对一条路径进行优化，最后一点一点的逼近最优解。