Pro.ID1380 Title经过指定顶点的最短路径 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1380 AC7 Submit23 Ratio30.43% 时间&空间限制描述给出一个有n个顶点的有向网,指定其中k个顶点(不含顶点1和顶点n)。求从顶点1到顶点n的,经过那k个顶点的最短路。 输入单测试用例。 输入的第一行是 顶点数n 和 弧数目e 。 1 ≤ n ≤ 40 ,1 ≤ e ≤ n×n 接下来是 e 行,每行三个整数 i , j , v ( 其中 0 < i, j ≤ n , 0 < v ≤ 100 ) ,表示从 顶点i 到 顶点j 的一条权值为v的弧。 接下来是一个正整数k ( 1 ≤ k ≤ n-2 ),接下来是k个正整数,表示必须经过的k个顶点。 输出Description 给出一个有n个顶点的有向网,指定其中k个顶点(不含顶点1和顶点n)。求从顶点1到顶点n的,经过那k个顶点的最短路。 Input 单测试用例。 输入的第一行是 顶点数n 和 弧数目e 。 1 ≤ n ≤ 40 ,1 ≤ e ≤ n×n 接下来是 e 行,每行三个整数 i , j , v ( 其中 0 < i, j ≤ n , 0 < v ≤ 100 ) ,表示从 顶点i 到 顶点j 的一条权值为v的弧。 接下来是一个正整数k ( 1 ≤ k ≤ n-2 ),接下来是k个正整数,表示必须经过的k个顶点。 Output 每个测试用例:如果不存在满足条件的路径,输出一行 "No solution"; 否则,输出两行:第1行,该最短路的长度;第2行从顶点1到顶点n的最短路,顶点之间用一个空格分隔,要求按路径的顶点次序,前一个顶点必须有弧指向后一个顶点。 Sample Input 5 12 Sample Output 140 Author 样例输入5 12 样例输出140 提示作者 |