2016华为软件精英挑战赛

[blaineyao]

前言
赛题源自“未来网络”业务发放中的路由计算问题。 算路问题属于基础算法问题，在图论、
网络、 交通等各个方面均有着广泛的研究与运用，里面不乏一些经典的算法，例如最短路中
的广度优先搜索， Dijkstra算法等。 网络算路问题的更优算法实现对于网络资源高效配置具
有重要价值。
1 问题定义
给定一个带权重的有向图 G=(V,E)， V 为顶点集， E 为有向边集，每一条有向边均有一个权
重。对于给定的顶点 s、 t，以及 V 的子集 V'，寻找从 s 到 t 的不成环有向路径 P，使得 P
经过 V'中所有的顶点(对经过 V'中节点的顺序不做要求)。
若不存在这样的有向路径 P，则输出无解，程序运行时间越短，则视为结果越优；若存在这
样的有向路径 P，则输出所得到的路径，路径的权重越小，则视为结果越优，在输出路径权
重一样的前提下，程序运行时间越短，则视为结果越优。