注：本文文字均摘自官方指定网站和论坛权威且可信，答疑见中间部分非常全，众玩家可放心阅读

同时文末给出了包括自己在内的诸多玩家的解法。

赛题源自“未來网络”业务发放中的路由计算问题算路问题属于基础算法问题，在图论、网络、交通等各个方面均有着广泛的研究与运用里面不乏┅些经典的算法，例如最短路中的广度优先搜索Dijkstra算法等。网络算路问题的更优算法实现对于网络资源高效配置具有重要价值

给定一个帶权重的有向图G=(V,E)，V为顶点集E为有向边集，每一条有向边均有一个权重对于给定的顶点s、t，以及V的子集V'寻找从s到t的不成环有向路径P，使得P经过V'中所有的顶点(对经过V'中节点的顺序不做要求)
若不存在这样的有向路径P，则输出无解程序运行时间越短，则视为结果越优；若存在这样的有向路径P则输出所得到的路径，路径的权重越小则视为结果越优，在输出路径权重一样的前提下程序运行时间越短，则視为结果越优

1）图中所有权重均为[1，20]内的整数；

个人吐槽：没有复权值经典Dijkstra算法可能适用
2）任一有向边的起点不等于终点；

个人吐槽：极端情况被踢出，减小难度

3）连接顶点A至顶点B的有向边可能超过一条其权重可能一样，也可能不一样；

个人吐槽：不一样就取较小者
4）该有向图的顶点不会超过600个每个顶点出度(以该点为起点的有向边的数量)不超过8；
5）V'中元素个数不超过50；

个人吐槽：指定点集越多，耗時越夸张难点之一，优化点之一
6）从s到t的不成环有向路径P是指，P为由一系列有向边组成的从s至t的有向连通路径且不允许重复经过任┅节点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和。

输出文件同样为一个.csv 文件。
1）如果该测试用例存在满足要求的有向路径P则按P 经过的有向边顺序，依次输出有向边的索引索引之间用'|'分割；
2）如果该测试用例不存茬满足要求的有向路径P，则输出两个字符NA；
3）只允许输出最多一条有向路径